#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
struct Query{
int t,i,ans,ord;
};
bool cmp1(Query&a,Query&b){
return a.t<b.t;
}
bool cmp2(Query&a,Query&b){
return a.ord<b.ord;
}
void solve(){
int n,q;
cin>>n>>q;
vector<int>init(n);
vector<int>nxt(n);
for(int&i:init)
cin>>i;
stack<pair<int,int>>st;
st.push({n+1,n});
for(int i=n-1;i>=0;i--){
while(st.top().first<init[i])
st.pop();
nxt[i]=st.top().second;
st.push({init[i],i});
}
vector<Query>qrs(q);
for(int i=0;i<q;i++)
qrs[i].ord=i;
for(auto&i:qrs){
cin>>i.t>>i.i;
i.t=min(i.t,n);
i.i--;
}
//sort(qrs.begin(),qrs.end(),cmp1);
set<pair<int,pair<int,int>>>s;
int sl=n;
vector<int>end(n,-1);
int end_end=n;
for(int curr=0;curr<n;){
s.insert({init[curr],{curr,nxt[curr]}});
curr=nxt[curr];
}
int cq=0;
for(int round=0;round<=n;round++){
while(sl-((--s.end())->second.second-(--s.end())->second.first)>=n/2){
int last_len=(--s.end())->second.second-(--s.end())->second.first;
sl-=last_len;
end_end-=last_len;
for(int i=0;i<last_len;i++)
end[end_end+i]=init[(--s.end())->second.first+i];
s.erase(--s.end());
}
/*if(cq<q&&qrs[cq].t==round){
vector<int>vec=end;
int ci=0;
for(auto i:s){
for(int j=i.second.first;j<i.second.second;j++){
vec[ci++]=init[j];
}
}
while(cq<q&&qrs[cq].t==round){
qrs[cq].ans=vec[qrs[cq].i];
cq++;
}
}*/
if(sl==n/2)
continue;
auto curr=(--s.end())->second;
s.erase(--s.end());
sl-=curr.second-curr.first;
auto nw=curr;
nw.second=nw.first+n/2-sl;
s.insert({init[nw.first],nw});
sl+=nw.second-nw.first;
curr.first=nw.second;
int prev=curr.first;
for(int i=curr.first+1;i<curr.second;i++){
if(init[i]>init[prev]){
s.insert({init[prev],{prev,i}});
sl+=i-prev;
prev=i;
}
}
s.insert({init[prev],{prev,curr.second}});
sl+=curr.second-prev;
}
//sort(qrs.begin(),qrs.end(),cmp2);
for(auto&i:qrs){
cout<<i.ans<<"\n";
}
}
int main(){
ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
//freopen("input.in","r",stdin);freopen("output.out","w",stdout);
int t=1;//cin>>t;
while(t--)solve();
return 0;
}
/*
6 3
1 5 6 2 3 4
1 2
0 4
1 5
2
2
5
6 6
2 1 5 4 6 3
0 1
1 1
0 3
1 3
0 6
10 6
2
2
5
4
3
3
10 10
7 5 2 9 10 8 4 3 6 1
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
2
3
6
1
7
5
8
4
9
10
*/
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:67:9: warning: unused variable 'cq' [-Wunused-variable]
67 | int cq=0;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
141 ms |
18156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3034 ms |
18256 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
909 ms |
6516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
141 ms |
18156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
