1 //CodeVS  2 //by Cydiater  3 //2016.9.11  4 #include <iostream>  5 #include <cstring>  6 #include <string>  7 #include <algorithm>  8 #include <queue>  9 #include <map> 10 #include <cstdio> 11 #include <cmath> 12 #include <ctime> 13 #include <iomanip> 14 #include <cstdlib> 15 using namespace std; 16 #define ll long long 17 #define up(i,j,n)        for(int i=j;i<=n;i++) 18 #define down(i,j,n)        for(int i=j;i>=n;i--) 19 const int MAXN=1e6+5; 20 const int oo=0x3f3f3f3f; 21 inline int read(){ 22     char ch=getchar();int x=0,f=1; 23     while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} 24     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 25     return x*f; 26 } 27 int N,a[MAXN],tol=0,root=0,ans=0; 28 struct SplayTree{ 29     int son[2],fa,v,siz,tag; 30 }t[MAXN]; 31 namespace solution{ 32     int get(int node){return t[t[node].fa].son[1]==node;} 33     void updata(int node){ 34         if(node){ 35             t[node].siz=1; 36             if(t[node].son[0])t[node].siz+=t[t[node].son[0]].siz; 37             if(t[node].son[1])t[node].siz+=t[t[node].son[1]].siz; 38         } 39     } 40     void downit(int node){ 41         if(t[node].tag){ 42             swap(t[node].son[0],t[node].son[1]); 43             t[t[node].son[0]].tag^=1;t[t[node].son[1]].tag^=1; 44             t[node].tag=0; 45         } 46     } 47     int get_node(int num){ 48         int now=root; 49         while(1){ 50             downit(now); 51             int tmp=(t[now].son[0]?t[t[now].son[0]].siz:0); 52             if(num==tmp+1)                        return now; 53             if(tmp>=num)now=t[now].son[0]; 54             else{ 55                 num-=(tmp+1); 56                 now=t[now].son[1]; 57             } 58         } 59     } 60     void rotate(int node){ 61         int old=t[node].fa,oldf=t[old].fa,which=get(node); 62         t[old].son[which]=t[node].son[which^1];t[t[old].son[which]].fa=old; 63         t[old].fa=node;t[node].son[which^1]=old;t[node].fa=oldf; 64         if(oldf)t[oldf].son[old==t[oldf].son[1]]=node; 65         updata(old);updata(node); 66     } 67     void splay(int node,int aim){ 68         for(int fa;(fa=t[node].fa);rotate(node)){ 69             if(node==aim)    break; 70             if(t[node].fa==aim){ 71                 rotate(node); 72                 break; 73             } 74             if(t[fa].fa==aim){ 75                 rotate(get(fa)==get(node)?fa:node); 76                 rotate(node); 77                 break; 78             } 79             rotate(get(fa)==get(node)?fa:node); 80         } 81         if(aim==root)root=node; 82     } 83     void build(int leftt,int rightt,int node,int fa){ 84         t[node].tag=0; 85         if(leftt==rightt){ 86             t[node].fa=fa;t[node].son[1]=t[node].son[0]=0; 87             t[node].v=a[leftt];t[node].siz=1; 88             return; 89         } 90         int mid=(leftt+rightt)>>1; 91         t[node].fa=fa;t[node].v=a[mid]; 92         if(leftt<=mid-1){ 93             t[node].son[0]=++tol; 94             build(leftt,mid-1,tol,node); 95         } 96         if(mid+1<=rightt){ 97             t[node].son[1]=++tol; 98             build(mid+1,rightt,tol,node); 99         }100         updata(node);101     }102     void init(){103         N=read();104         up(i,2,N+1)a[i]=read();a[1]=oo;a[N+2]=oo;105         root=1;106         build(1,N+2,++tol,0);107     }108     void slove(){109         while(1){110             int node=get_node(2);111             if(t[node].v==1)break;112             int k=t[node].v;113             //cout<<k<<endl;114             int leftt=get_node(1),rightt=get_node(k+2);115             splay(leftt,root);splay(rightt,t[root].son[1]);116             int son=t[root].son[1];t[t[son].son[0]].tag^=1;117             if(++ans==100000){118                 ans=-1;119                 break;120             }121         }122     }123     void output(){124         cout<<ans<<endl;125     }126 }127 int main(){128     //freopen("input.in","r",stdin);129     using namespace solution;130     init();131     slove();132     output();133     return 0;134 }