1 #include<cstdio>
2 const int maxn=3e5;
3 void swap_(int&x,int&y){x^=y,y^=x,x^=y;}
4 int n,m,hd,rt;
5 int t[maxn],d[maxn],f[maxn],sz[maxn],id[maxn],s[maxn][2];
6 void pushdown(int k){swap_(s[k][0],s[k][1]),t[s[k][0]]^=1,t[s[k][1]]^=1,t[k]=0;}
7 void rot(int&k,int x){
8 int y=f[x],z=f[y],l,r;
9 l=s[y][0]==x?0:1,r=l^1;
10 if(y==k) k=x;
11 else{
12 if(s[z][0]==y) s[z][0]=x;
13 else s[z][1]=x;
14 }
15 f[x]=z,f[y]=x,f[s[x][r]]=y;
16 s[y][l]=s[x][r],s[x][r]=y;
17 sz[y]=sz[s[y][0]]+sz[s[y][1]]+1;
18 sz[x]=sz[s[x][0]]+sz[s[x][1]]+1;
19 }
20 void splay(int&k,int x){while(x!=k) rot(k,x);}
21 int find(int k,int x){
22 if(t[k]) pushdown(k);
23 int l=s[k][0],r=s[k][1];
24 if(sz[l]+1==x) return k;
25 if(sz[l]>=x) return find(l,x);
26 else return find(r,x-sz[l]-1);
27 }
28 void rever(int l,int r){
29 int x=find(rt,l),y=find(rt,r+2);
30 splay(rt,x),splay(s[x][1],y);
31 int z=s[y][0];
32 t[z]^=1;
33 }
34 void build(int l,int r,int fa){
35 if(l>r) return;
36 int now=id[l],last=id[fa];
37 if(l==r){
38 f[now]=last,sz[now]=1;
39 if(l<fa) s[last][0]=now;
40 else s[last][1]=now;
41 return;
42 }
43 int mid=l+r>>1;now=id[mid];
44 build(l,mid-1,mid);
45 build(mid+1,r,mid);
46 f[now]=last;
47 sz[mid]=sz[s[mid][0]]+sz[s[mid][1]]+1;
48 if(mid<fa) s[last][0]=now;
49 else s[last][1]=now;
50 }
51 int main(){
52 scanf("%d",&n);
53 for(int i=1;i<=n+2;i++) id[i]=++hd;
54 d[1]=-1e9;d[n+1]=1e9;
55 for(int i=2;i<=n+1;i++) scanf("%d",&d[i]);
56 build(1,n+2,0);
57 rt=(n+3)>>1;
58 scanf("%d",&m);
59 for(int i=1;i<=m;i++){
60 int l,r;
61 scanf("%d%d",&l,&r);
62 rever(l,r);
63 }
64 for(int i=2;i<=n+1;i++) printf("%d ",d[find(rt,i)]);
65 return 0;
66 }
