You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

初始给你一个排列p[i],你可以执行以下操作任意多次。

选择一个i，交换p[i]和p[i+1]的值（其实就是交换排列当中两个相邻的元素）。

我们现在希望对于任意的i满足p[i]不等于i，求最少需要执行的操作次数。

【输入格式】

输入文件A.in。

第一行一个整数n。

第二行n个整数，其中第i个整数表示p[i]。

【输出格式】

输出文件A.out

一行一个整数表示最少的操作次数。

【样例输入1】

5

1 4 3 5 2

【样例输出1】

2

【样例输入2】

2

1 2

【样例输出2】

1

【样例输入3】

9

1 2 4 9 5 8 7 3 6

【样例输出3】

3

【数据范围】

对于 30% 数据 n<=10

对于 50% 数据 n<=1000

对于 100% 数据n<=100000