提示: 欢迎访问OurACM平台。
Problem 2166 inversion

Accept: 60    Submit: 157
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

给一个整数序列a1,a2,a3…,an,其逆序数对数为满足 i<j 且 ai>aj 的(i,j)对数。现可以交换其中两个数的位置,问改变后的序列的逆序数对数最小是多少?若不存在一种交换使得序列的逆序数对数变小则答案为原来的逆序数对数。

Input

输入包含多组数据。对于每组数据,第一行输入一个整数N (2<=N <=1000),表示序列包含N个整数,第二行依次输入N个整数表示序列a1,a2,a3…,an。

Output

对于每组数据输出一个整数,表示交换某两个数或者不交换能得到的最小的逆序数对数。

Sample Input

3 3 1 2 3 1 2 3

Sample Output

1 0

Submit  Back  Status  Discuss