Problem E: 数组排序

Problem E: 数组排序

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

  小明的老师给小明布置了一个作业,让他使一个大小为n的数组a进行降序排序(该数组的元素是1到n的数,每个数只出现一次),最少需要进行多少次操作。
  不过老师规定了操作规则,选择a的某个子数组(连续的子段),然后按任何方式重新排列其中的元素,但是这个操作不能应用于整个数组(也就是不能选择整个区间[1,n])。
  例如数组a=[4,1,2,5,3],可以选择区间[1,3]进行重新排列,可以得到a=[1,2,4,5,3](这只是其中一中情况)也可以变成a=[1,4,2,5,3];
  小明需要你来帮助他解决这个问题,计算上述操作的最小数目,以便按降序对排列a进行排序。

Input

第一行包含一个整数n(1 ≤ n ≤ 1000,n不为2)表示排列中的元素数。
第二行包含n个从1到n的不同整数,表示给定的排列a。

Output

输出一个整数(数组a按降序排列的最小操作数)

Sample Input Copy

样例输入1:
10
10 1 2 3 4 5 6 7 8 9

样例输入2:
5
5 4 3 2 1

样例输入3:
4
2 1 4 3

Sample Output Copy

样例输出1:
1

样例输出2:
0

样例输出3:
2