数据结构基础

【题目描述】无限轮回（samsara）HDU 1394

一个序列a₁，a₂，…，a_n，那么该序列的逆序数是这么一对数（a_i，a_j），其中 i ＜ j 并且 a_i＞ a_j。如2431中，（2，1），（4，3），（4，1），（3，1）是逆序，逆序对数是4。

对于一个给定的序列a₁， a₂，…， a_n， 如果我们移动第m（m≥0）个数到序列末尾，则会获得另一个序列，例如n的序列的全部序列如下：

a₁， a₂，…， a_n-1， a_n (初始序列，即 m＝0 )

a₂， a₃，…， a_n， a₁ (当 m＝1时)

a₃， a₄，…，a_n，a₁， a₂ (当 m＝2时)

……

a_n，a₁，a₂，…， a_n-1 (当 m＝n－1时)

请从上述所有排列中，找出最少的逆序对数。

【输入格式】

每组测试数据包括两行，第一行为整数 n (n≤5 000)，第二行为从0到n－1的n个整数的排列。

【输出格式】

每一组测试数据，输出最少逆序数。

【输入样例】

10

1 3 6 9 0 8 5 7 4 2

【输出样例】

16

【样例说明】

当序列为4 2 1 3 6 9 0 8 5 7时，有（4，2），（4，1），（4，3），（4，0），（2，1），（2，0），（1，0），（3，0），（6，0），（6，5），（9，0），（9，8），（9，5），（9，7），（8，5），（8，7）共16对逆序数。