409004 - 序列的逆序数

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

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

a_1， a_2，…， a_{n-1}， a_n (初始序列，即 m＝0 )

a_2， a3_，…， a_n， a_1 (当 m＝1时)

a_3， a_4，…，a_n，a_1， a_2 (当 m＝2时)

……

a_n，a_1，a_2，…， a_{n-1} (当 m＝n－1时)

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

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

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

当序列为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对逆序数。