#pragma GCC optimize("O3,unroll-loops,fast-math") #include <bits/stdc++.h> using namespace std; #define int long long #define ll long long #define pb push_back #define pii pair<int,int> #define sz(v) (int)v.size() #define fi first #define se second #define INF 1223372036854775807 #define INF2 122337203 #define MOD 998244353 #define cint(x) int x;cin>>x; #define cinarr(a,n) int a[n];for (int i=0;i<n;i++) cin>>a[i]; #define coutarr(a) for (auto d:a)cout<<d<<" "; cout<<endl; #define coutarrD(a) for (auto d:a) cout<<d.fi<<","<<d.se<<" "; cout<<endl; #define BERKAY_TUP ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define endl '\n' #define ld long double #define mid (start+end)/2 #define vvi vector<vector<int>> int t=1; int interactive=0; int usaco=0; int testCase=0; int a[200023]; int tree[800023]; void update(int n,int start,int end,int x,int v){ if(start>end || start>x || end<x) return; if (start>=x && end<=x){ tree[n]=v; return; } update(n*2,start,mid,x,v); update(n*2+1,mid+1,end,x,v); tree[n]=tree[n*2]+tree[n*2+1]; } int f=0; pii fin(int n,int start,int end,int k){ if (start==end) return {start,tree[n]}; if (tree[n*2]>=k) return fin(n*2,start,mid,k); else{ f+=tree[n*2]; return fin(n*2+1,mid+1,end,k-tree[n*2]); } } int revP[200023]; void solve(){ int n,q; cin>>n>>q; vector<pair<pii,int>> qu; for (int i=1;i<=n;i++) cin>>a[i]; for (int i=1;i<=n;i++) revP[a[i]]=i; for (int i=0;i<q;i++){ int t,x; cin>>t>>x; qu.pb({{t,x},i}); } sort(qu.begin(),qu.end()); int c=1; int x=0; int xv=0; for (int i=1;i<=n/2;i++){ if (a[i]>xv){ if (xv!=0){ update(1,1,n,xv,x); //cout<<xv<<" "<<x<<endl; } xv=a[i]; x=1; } else x++; } if (xv!=0){ update(1,1,n,xv,x); //cout<<xv<<" "<<x<<endl; } xv=0,x=0; for (int i=n/2+1;i<=n;i++){ if (a[i]>xv){ if (xv!=0){ update(1,1,n,xv,x); //cout<<xv<<" "<<x<<endl; } xv=a[i]; x=1; } else x++; } if (xv!=0){ update(1,1,n,xv,x); //cout<<xv<<" "<<x<<endl; } int ans[q]; bool fl=false; for (int i=0;i<q;i++){ auto d=qu[i]; if (d.fi.fi==0) ans[d.se]=a[d.fi.se]; else{ while (d.fi.fi>c && !(fl)){ //cout<<"b"<<endl; f=0; pii j=fin(1,1,n,n/2); int g=j.se-(n/2-f); xv=0; int cc=0; for (int i=revP[j.fi]+(n/2-f);i<=revP[j.fi]+j.se-1;i++){ if (a[i]>xv){ if (xv!=0){ update(1,1,n,xv,x); cc++; //cout<<"a"<<xv<<" "<<x<<endl; } xv=a[i]; x=1; } else x++; } if (xv!=0){ update(1,1,n,xv,x); cc++; //cout<<"a"<<xv<<" "<<x<<endl; } update(1,1,n,j.fi,n/2-f); c++; if (cc==0) fl=true; } f=0; pii j=fin(1,1,n,d.fi.se); int k=d.fi.se; //cout<<"*"<<j.fi<<" "<<f<<endl; ans[d.se]=a[revP[j.fi]+k-f-1]; } } for (int d:ans) cout<<d<<endl; } int32_t main(){ BERKAY_TUP; if (usaco){ freopen("team.in", "r", stdin); freopen("team.out", "w", stdout); } if (!interactive){ #ifdef Local freopen("in.txt", "r", stdin); freopen("out2.txt", "w", stdout); //freopen("wormsort.out", "w", stdout); #endif } if (t==1) solve(); else{ cin>>t; while (t--){testCase++;solve();} } return 0; }

Main.cpp: In function 'int32_t main()':
Main.cpp:152:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |         freopen("team.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:153:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |         freopen("team.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~