1 #include<cstdio>  2 #include<cstdlib>  3 #include<cmath>  4 #include<cstring>  5 #include<algorithm>  6 #include<iostream>  7 #include<vector>  8 #include<map>  9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 200000+5 14 #define maxm 500+100 15 #define eps 1e-10 16 #define ll long long 17 #define pa pair<int,int> 18 #define for0(i,n) for(int i=0;i<=(n);i++) 19 #define for1(i,n) for(int i=1;i<=(n);i++) 20 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 21 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 22 #define mod 1000000007 23 using namespace std; 24 inline int read() 25 { 26     int x=0,f=1;char ch=getchar(); 27     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 28     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 29     return x*f; 30 } 31 int n,rt,t1,t2,a[maxn],b[maxn],fa[maxn],c[maxn][2],mi[maxn][2],s[maxn]; 32 bool rev[maxn]; 33 inline void pushup(int x) 34 { 35     int l=c[x][0],r=c[x][1]; 36     s[x]=s[l]+s[r]+1; 37     mi[x][0]=a[x];mi[x][1]=s[l]+1; 38     if(mi[x][0]>mi[l][0])mi[x][0]=mi[l][0],mi[x][1]=mi[l][1]; 39     if(mi[x][0]>mi[r][0])mi[x][0]=mi[r][0],mi[x][1]=s[l]+1+mi[r][1]; 40 } 41 inline void rotate(int x,int &k) 42 { 43     //cout<<x<<‘ ‘<<k<<" AAAAAA"<<endl; 44     int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1; 45     if(y!=k)c[z][c[z][1]==y]=x;else k=x; 46     fa[x]=z;fa[y]=x;fa[c[x][r]]=y; 47     c[y][l]=c[x][r];c[x][r]=y; 48     pushup(y);pushup(x); 49 } 50 inline void splay(int x,int &k) 51 { 52     while(x!=k) 53     { 54         int y=fa[x],z=fa[y]; 55         if(y!=k) 56         { 57             if(c[z][0]==y^c[y][0]==x)rotate(x,k);else rotate(y,k); 58         } 59         rotate(x,k); 60     } 61 } 62 inline void rever(int x) 63 { 64     if(!x)return; 65     rev[x]^=1; 66     swap(c[x][0],c[x][1]); 67     mi[x][1]=s[x]+1-mi[x][1]; 68 } 69 inline void pushdown(int x) 70 { 71     if(!x)return; 72     if(!rev[x])return; 73     rever(c[x][0]);rever(c[x][1]); 74     rev[x]=0; 75 } 76 inline int find(int x,int k) 77 { 78     pushdown(x); 79     int l=c[x][0],r=c[x][1]; 80     if(s[l]+1==k)return x; 81     else if(s[l]>=k)return find(l,k); 82     else return find(r,k-s[l]-1); 83 } 84 inline void split(int l,int r) 85 { 86     t1=find(rt,l);t2=find(rt,r); 87     splay(t1,rt);splay(t2,c[t1][1]); 88 } 89 inline void build(int l,int r,int f) 90 { 91     if(l>r)return; 92     int x=(l+r)>>1; 93     fa[x]=f;c[f][x>f]=x; 94     if(l==r){s[x]=1;mi[x][0]=a[x];mi[x][1]=1;return;} 95     build(l,x-1,x);build(x+1,r,x); 96     pushup(x); 97 } 98 inline bool cmp(int x,int y){return a[x]==a[y]?x<y:a[x]<a[y];} 99 int main()100 {101     freopen("input.txt","r",stdin);102     freopen("output.txt","w",stdout);103     n=read();104     for2(i,2,n+1)a[i]=read(),b[i]=i;105     sort(b+2,b+n+2,cmp);106     for2(i,2,n+2)a[b[i]]=i;107     a[1]=a[n+2]=n+n;mi[0][0]=inf;108     build(1,n+2,0);rt=(1+n+2)>>1;109     for1(i,n)110     {111         //cout<<mi[rt][1]<<endl;112         int x=find(rt,mi[rt][1]);113         printf("%d",(n-(s[rt]-mi[rt][1]-1)));114         if(i!=n)printf(" ");115         //cout<<x<<endl;116         split(1,mi[rt][1]+1);117         rever(c[t2][0]);118         pushup(t2);pushup(t1);119         split(1,3);120         //cout<<"AAAAAAA"<<‘ ‘<<a[c[t2][0]]<<endl;121         c[t2][0]=0;122         pushup(t2);pushup(t1);  123     }124     printf("\n");125     return 0;126 }