1. Description
Tin 是一位著名的魔术师，他的一个经典魔术与洗牌有关。
Tin 会准备一套牌，总共 \(n\) 张（保证 \(n\) 为偶数），各编号为 \(1\sim n\)，一开始的时候牌是乱的且倒扣在桌子上。紧接着他开始表演洗牌，在洗牌的任意时刻，观众都可以向 Tin 询问从底往上数第 \(t\) 张牌是什么牌，很显然 Tin 一定会立即回答出正确答案。
事实上，Tin 采用如下方式来完成这个魔术，首先他记下了一开始的 \(n\) 张牌的顺序，接着采用如下技巧洗牌：
- 拿起自顶向下 \(\frac{n}{2}\) 张牌放在右手，自底向上 \(\frac{n}{2}\) 张牌放在左手，牌的正面对着桌子。
- 借助他的记忆，将左右手最底下的牌进行比较，将编号较小的那张牌放下，重复这个操作直到左右手一边为空。
- 将还有牌的那只手上的所有牌放下。
请你写一个程序模拟 Tin 的魔术。
2. Solution
首先需要观察。
不妨假设，Tin 左手上的 \(\frac{n}{2}\) 张牌的值为 \(\{a_i\}\)，右手上的 \(\frac{n}{2}\) 张牌的值为 \(\{b_i\}\)，此时左手过到第 \(i\) 张牌，右手过到第 \(j\) 张牌，且 \(a_i<b_j\)（反之同理）。
因为 \(a_i<b_j\)，所以 \(a_i\) 后面一串小于 \(a_i\) 的值同样小于 \(b_j\)，所以从 \(i\) 到下一张值比 \(a_i\) 大的牌之间的这一段都会被直接放下去。
这个观察启示我们，要将按照前缀最大值将整个序列分成若干段。
则一次操作相当于：将序列分成两份，然后将两段的前缀最大值排序。
进一步，我们可以想到，整个序列的前缀最大值本来就是有序的，不有序的地方只有在中间分开之后新产生的前缀最大值。
所以一次操作如下：我们找到跨过 \(\frac{n}{2}\) 这个位置的段，然后将它分成若干个新段再重新加入序列。
如何将一整段分成若干个新段？
不难想到，在 \(\frac{n}{2}\) 前的部分单独为一段，然后 \(\frac{n}{2}\) 后面的这一部分一定和原序列中的对应部分的序列是一样的，所以，我们在原序列上预处理出 \(nxt_i\) 表示 \(i\) 右边第一个比 \(i\) 大的位置，接着暴力跳 \(nxt_i\) 就可以了，很显然，每一个位置只会被跳一次，所以时间复杂度仍然正确。
同时，我们就可以证明，最多经过 \(n\) 次操作，整个序列就不会发生变化。原因是，如果某一次操作，没有产生新的前缀最大值，那么说明此时序列中不存在跨过 \(\frac{n}{2}\) 的段，所以序列一定不发生变化，否则，每一个位置，最多成为一次新增的前缀最大值，所以最多也只有 \(n\) 次操作。
用随便什么数据结构维护整个序列，就可以做到 \(O(n\log n)\) 的时间复杂度。
询问也很简单，在此不过多赘述。
3. Code
/*by ChenMuJiu*/
/*略去缺省源与快读快写*/
const int N=2e5+5,M=1e6+5;
int n,m,top;
int ans[M],c[N],pos[N],nxt[N],st[N];
vector<pii>b[N];
mt19937 ran(time(0));
struct Node{int val,len,dis;
};
struct Treap{int num,rt;int val[N<<1],len[N<<1],sum[N<<1],ch[N<<1][2];unsigned int c[N<<1];int New(int _val=0,int _len=0){int p=++num;val[p]=_val,len[p]=_len,sum[p]=_len;ch[p][0]=0,ch[p][1]=0;c[p]=ran();return p;}void pushup(int p){sum[p]=sum[ch[p][0]]+len[p]+sum[ch[p][1]];}pii split(int p,int v){if(!p)return {0,0};if(val[p]<=v){pii tmp=split(ch[p][1],v);ch[p][1]=tmp.first;pushup(p);return {p,tmp.second};}else{pii tmp=split(ch[p][0],v);ch[p][0]=tmp.second;pushup(p);return {tmp.first,p};}}int merge(int x,int y){if(x==0&&y==0)return 0;if(x==0)return y;if(y==0)return x;if(c[x]<c[y]){ch[x][1]=merge(ch[x][1],y);pushup(x);return x;}else{ch[y][0]=merge(x,ch[y][0]);pushup(y);return y;}}pii find(int p,int k){if(sum[ch[p][0]]>=k)return find(ch[p][0],k);k-=sum[ch[p][0]];if(len[p]>=k)return {k,p};k-=len[p];return find(ch[p][1],k);}void insert(int _val,int _len){int p=New(_val,_len);pii tmp=split(rt,_val-1);rt=merge(tmp.first,merge(p,tmp.second));}void erase(int _val){pii tmp1=split(rt,_val-1);pii tmp2=split(tmp1.second,_val);rt=merge(tmp1.first,tmp2.second);}Node query(int k){pii tmp=find(rt,k);return {val[tmp.second],len[tmp.second],tmp.first};}
}treap;
signed main(){read(n),read(m);for(int i=1;i<=n;i++)read(c[i]);for(int i=1,t,p;i<=m;i++){read(t),read(p);if(t==0){ans[i]=c[p];continue;}tomin(t,n);b[t].push_back({p,i});}st[0]=n+1;for(int i=n;i>=1;i--){pos[c[i]]=i;while(top&&c[st[top]]<c[i])top--;nxt[i]=st[top];st[++top]=i;}for(int i=1;i<=n;i=nxt[i])treap.insert(c[i],nxt[i]-i);for(int i=1;i<=n;i++){Node tmp=treap.query(n>>1);treap.erase(tmp.val);treap.insert(tmp.val,tmp.dis);int R=pos[tmp.val]+tmp.len-1;for(int j=pos[tmp.val]+tmp.dis;j<=R;j=nxt[j]){treap.insert(c[j],min(R+1,nxt[j])-j);}for(auto tmp:b[i]){Node res=treap.query(tmp.first);ans[tmp.second]=c[pos[res.val]+res.dis-1];}}for(int i=1;i<=m;i++)write(ans[i]),Nxt;
}