codeforces #323 div 2 B. Robot's Task(又是暴力？

Robot Doc is located in the hall, with n computers stand in a line, numbered from left to right from 1 to n. Each computer contains exactly one piece of information, each of which Doc wants to get eventually. The computers are equipped with a security system, so to crack the i-th of them, the robot needs to collect at least ai any pieces of information from the other computers. Doc can hack the computer only if he is right next to it.

The robot is assembled using modern technologies and can move along the line of computers in either of the two possible directions, but the change of direction requires a large amount of resources from Doc. Tell the minimum number of changes of direction, which the robot will have to make to collect all n parts of information if initially it is next to computer with number 1.

It is guaranteed that there exists at least one sequence of the robot's actions, which leads to the collection of all information. Initially Doc doesn't have any pieces of information.

Input

The first line contains number n (1 ≤ n ≤ 1000). The second line contains n non-negative integersa1, a2, ..., an (0 ≤ ai < n), separated by a space. It is guaranteed that there exists a way for robot to collect all pieces of the information.

Output

Print a single number — the minimum number of changes in direction that the robot will have to make in order to collect all n parts of information.

Sample test(s)

input

3
0 2 0

output

input

5
4 2 3 0 1

output

input

7
0 3 1 0 5 2 6

output

Note

In the first sample you can assemble all the pieces of information in the optimal manner by assembling first the piece of information in the first computer, then in the third one, then change direction and move to the second one, and then, having 2 pieces of information, collect the last piece.

In the second sample to collect all the pieces of information in the optimal manner, Doc can go to the fourth computer and get the piece of information, then go to the fifth computer with one piece and get another one, then go to the second computer in the same manner, then to the third one and finally, to the first one. Changes of direction will take place before moving from the fifth to the second computer, then from the second to the third computer, then from the third to the first computer.

In the third sample the optimal order of collecting parts from computers can look like that: 1->3->4->6->2->5->7.

一开始打算找规律...

推一般性结论．．

试着交了一发...wa了．．

然后发现n只有１０００...大力出奇迹．．．

就算每次每弄一个就要掉头...也就是最坏情况...也不过　O(N2)的复杂度...不过1e6

于是暴力写了下...然后就A了.233

 1 /*************************************************************************
 2     > File Name: code/cf/#323/BB.cpp
 3     > Author: 111qqz
 4     > Email: rkz2013@126.com 
 5     > Created Time: 2015年10月04日 星期日 01时07分59秒
 6  ************************************************************************/
 7 
 8 #include<iostream>
 9 #include<iomanip>
10 #include<cstdio>
11 #include<algorithm>
12 #include<cmath>
13 #include<cstring>
14 #include<string>
15 #include<map>
16 #include<set>
17 #include<queue>
18 #include<vector>
19 #include<stack>
20 #include<cctype>
21                  
22 #define yn hez111qqz
23 #define j1 cute111qqz
24 #define ms(a,x) memset(a,x,sizeof(a))
25 using namespace std;
26 const int dx4[4]={1,0,0,-1};
27 const int dy4[4]={0,-1,1,0};
28 typedef long long LL;
29 typedef double DB;
30 const int inf = 0x3f3f3f3f;
31 const int N=1E3+7;
32 int a[N];
33 bool vis[N];
34 int n;
35 int main()
36 {
37   #ifndef  ONLINE_JUDGE 
38    freopen("in.txt","r",stdin);
39   #endif
40    cin>>n;
41    for ( int i = 1 ; i<= n ;i++) scanf("%d",&a[i]);
42    int cnt = 0 ;
43    int dir = 1;
44    int ans = 0 ;
45    ms(vis,false);
46    while (cnt<n)
47    {
48        if (ans%2==0)
49        {
50        for ( int i = 1 ; i <= n ; i++)
51         {
52         if (cnt>=a[i]&&!vis[i])
53         {
54             cnt++;
55             vis[i] = true;
56         }
57         }
58 //       cout<<"cnt111:"<<cnt<<endl;
59        }
60        else
61     {
62         for ( int i = n ; i >=1 ; i--)
63         {
64         if (cnt>=a[i]&&!vis[i])
65         {
66             cnt++;
67             vis[i] = true;
68         }
69         }
70 //        cout<<"cnt2 "<<cnt<<endl;
71     }
72        ans++;
73   //     cout<<"cnt:"<<cnt<<" ans:"<<ans<<endl;
74    }
75    
76    cout<<ans-1<<endl;
77    
78   
79    
80  #ifndef ONLINE_JUDGE  
81   fclose(stdin);
82   #endif
83     return 0;
84 }

View Code