描述


定义一种循环有序序列，该序列可看做首尾相连的圈状序列，从某个位置开始向后数至该位置的前一位，数过的元素都是从小到大排序的。例如对于1,2,3,4这四个数，符合条件的循环有序序列有1,2,3,4；2,3,4,1；3,4,1,2；4,1,2,3四个。

定义一种操作，可以在序列里任选一个位置的数，把它移动到序列的第一个位置，例如序列1,2,3,4，对3进行操作后序列变为3,1,2,4。

现在输入一个长度为n的初始序列，问至少经过多少次操作可以使原序列变成一个循环有序序列。

输入


输入文件只有一组数据。第一行一个整数N(1<=N<=30000)。第二行N个整数Ai（1<=Ai<=N），满足对于任意的i!=j,保证Ai!=Aj，即1~N的一个排序。

输出


输出文件只有一行，包含一个整数，表示至少需要的操作次数。

样例输入

4
3 2 4 1
样例输出

1
提示


对于3,2,4,1存在四种循环有序序列，需要的操作次数分别为：

1,2,3,4    2次

2,3,4,1    1次

3,4,1,2    3次

4,1,2,3    3次

所以最少的操作次数为1次。

输入输出说明

对于20%的数据，N<=20。

对于40%的数据，N<=500。

对于70%的数据，N<=5000。

对于100%的数据，N<=30000。

题目来源

2007年全国青少年信息学竞赛广东队组队选拔赛

友情链接:
每天一题坚持一个月....之四
http://bbs.itheima.com/thread-45153-1-1.html
每天一题坚持一月....之三
http://bbs.itheima.com/thread-44986-1-1.html
每天一题坚持一个月....之二
http://bbs.itheima.com/thread-44819-1-1.html
每天一题坚持一个月....之一
http://bbs.itheima.com/thread-44753-1-1.html

抢钱抢粮抢清新

寒哥 求答案~！

强大。。。。。。。。。

1. class Main
   
2. {
   
3.         public static void main(String[] args)
   
4.         {
   
5.                     Scanner cin = new Scanner(System.in);
   
6.                     while(cin.hasNext())
   
7.                     {
   
8.                             int n = cin.nextInt();
   
9.                             int[] ans, tmp;
   
10.                             int  Max=0, i=0, p=0, tot=0, j=0;
    
11.                             ans = new int[n+1];
    
12.                             tmp = new int[n+1];
    
13.                             for(i=1;i<=n;i++)// 这个地方的用法很有趣 有兴趣可以把 tmp 打印出来
    
14.                             {
    
15.                                     ans[i]=cin.nextInt();
    
16.                                     tmp[ans[i]]=i;
    
17.                             }
    
18.                             Max=0; i=1; p=1; tot=1;
    
19.                             int temp;
    
20.                             while(i<n)// 利用逆序数  
    
21.                             {
    
22.                                     temp = ans[p]+1;
    
23.                                     if(temp>n) temp = 1;
    
24.                                     j =  tmp[temp];
    
25.                                     if(j>p)tot++;
    
26.                                     else tot=1;
    
27.                                     Max = Math.max(Max, tot);
    
28.                                     p=j;
    
29.                                    
    
30.                                     i++;
    
31.                             }
    
32.                             System.out.println(n-Max);
    
33.                     }
    
34.         }
    
35. }

复制代码