测试数据来自 system/1893

背景

PS: Pascal代码

procedure bubble_sort(n:longint);
var
i,j,x:longint;
begin
for i:=0 to n-1 do
for j:=0 to n-1 do
if a[j]>a[j+1] then
begin
x:=a[j];
a[j]:=a[j+1];
a[j+1]:=x;
end;
end;

描述

这是一道良心的签到题。
冒泡排序大家都会。
对于一个有 N 个元素的排列 A ，你需要选择任意两个元素交换一次且仅一次，得到新序列 A' ，使 A‘ 用以下冒泡排序排序时的交换次数最小，输出答案。

void bubble_sort(int a, int n)
{
int i, j;
for (i = 0; i < n - 1; i ++)
{
for (j = 0; j < n - 1; j ++)
{
if (a[j] > a[j + 1])
{
/你懂得…………*/
int x = a[j];
a[j] = a[j + 1];
a[j + 1] = x;
}
}
}
}

格式

输入格式

第一行一个整数 N 。
第二行 N 个整数 Ai 。

输出格式

输出一个数表示答案。

样例1

样例输入1

5
10
3
6
8
1

样例输出1

0

样例2

样例输入2

5
3
1
7
9
5

样例输出2

2

样例3

样例输入3

3
1
2
3

样例输出3

1

限制

对于 10% 的数据：
1 ≤ N ≤ 1 000

对于 100% 的数据：
1 ≤ N ≤ 100 000
1 ≤ Ai ≤ 1 000 000 000

提示

样例解释1：
A'={1, 3, 6, 8, 10} 已经有序，冒泡排序时不需交换
2:
A'={1, 3, 2} （注意必须数列A必须进行一次交换得到A'）冒泡排序交换了一次

来源

布吉岛。