#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
const int nmax=2e5+42;
int my_n,my_k;
int inp[nmax];
struct info
{
int mini,lazy;
int pos;
};
info tree[4*nmax];
void push(int node)
{
tree[node*2].lazy+=tree[node].lazy;
tree[node*2+1].lazy+=tree[node].lazy;
tree[node].lazy=0;
}
info actual(info a)
{
a.mini+=a.lazy;
a.lazy=0;
return a;
}
info my_merge(info a,info b)
{
a=actual(a);
b=actual(b);
if(a.mini<b.mini)return a;
if(a.mini>b.mini)return b;
if(b.pos-a.pos<=my_k-1)return a;
return b;
}
void build(int node,int l,int r)
{
if(l==r)
{
tree[node].mini=inp[l];
tree[node].lazy=0;
tree[node].pos=l;
return;
}
int av=(l+r)/2;
build(node*2,l,av);
build(node*2+1,av+1,r);
tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}
void update(int node,int l,int r,int lq,int rq,int val)
{
if(l==lq&&r==rq)
{
tree[node].lazy+=val;
return;
}
push(node);
int av=(l+r)/2;
if(lq<=av)update(node*2,l,av,lq,min(av,rq),val);
if(av<rq)update(node*2+1,av+1,r,max(av+1,lq),rq,val);
tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}
int outp[2*nmax];
set<int> zeros,legit;
void test(int pos)
{
if(zeros.size()==1)
{
legit.insert(pos);
return;
}
set<int>::iterator it=zeros.lower_bound(pos);
if(it==zeros.begin())it=zeros.end();
it--;
int prv=*it;
if(prv>pos)prv=prv-my_n;
//cout<<"testing "<<pos<<" : prv= "<<prv<<endl;
if(pos-prv>=my_k)legit.insert(pos);
}
void add(int pos)
{
if(zeros.size()==0)
{
zeros.insert(pos);
legit.insert(pos);
return;
}
zeros.insert(pos);
set<int>::iterator it=zeros.lower_bound(pos);
it++;
if(it==zeros.end())it=zeros.begin();
int nxt=*it;
legit.erase(nxt);
test(nxt);
test(pos);
}
void sub(int pos)
{
legit.erase(pos);
zeros.erase(pos);
if(zeros.size()==0)
{
return;
}
set<int>::iterator it=zeros.lower_bound(pos);
if(it==zeros.end())it=zeros.begin();
test(*it);
}
int pref[nmax];
vector< pair<int/*outp*/,int/*id*/> > tree_merge[4*2*nmax];
int query(int node,int l,int r,int lq,int rq,int val)//position of the highest in [lq, rq] up to val
{
if(l==lq&&r==rq)
{
//cout<<"query "<<node<<" "<<lq<<" "<<rq<<" "<<val<<endl;
int p=lower_bound(tree_merge[node].begin(),tree_merge[node].end(),make_pair(val,0))-tree_merge[node].begin();
p--;
if(p<0)return -1;
//cout<<"p= "<<p<<" merge= "<<tree_merge[node][p].first<<" , "<<tree_merge[node][p].second<<endl;
return tree_merge[node][p].second;
}
int ret=-1;
int av=(l+r)/2;
if(lq<=av)
{
int help=query(node*2,l,av,lq,min(av,rq),val);
if(ret==-1)ret=help;
}
if(av<rq)
{
int help=query(node*2+1,av+1,r,max(av+1,lq),rq,val);
if(ret==-1)ret=help;
else if(help!=-1)
{
if(outp[ret]<outp[help])ret=help;
}
}
return ret;
}
void build_merge(int node,int l,int r)
{
if(l==r)
{
tree_merge[node].push_back({outp[l],l});
/*
cout<<node<<" "<<l<<" "<<r<<" : ";
for(auto w:tree_merge[node])cout<<w.first<<" "<<w.second<<"\t";cout<<endl;
*/
return;
}
int av=(l+r)/2;
build_merge(node*2,l,av);
build_merge(node*2+1,av+1,r);
tree_merge[node]=tree_merge[node*2];
for(auto w:tree_merge[node*2+1])tree_merge[node].push_back(w);
sort(tree_merge[node].begin(),tree_merge[node].end());
/*
cout<<node<<" "<<l<<" "<<r<<" : ";
for(auto w:tree_merge[node])cout<<w.first<<" "<<w.second<<"\t";cout<<endl;
*/
}
int go_left[20][2*nmax],go_right[20][2*nmax];
void init(int k, std::vector<int> r) {
my_n=r.size();
my_k=k;
for(int i=1;i<=my_n;i++)inp[i]=r[i-1];
for(int i=1;i<=my_n;i++)pref[i]=pref[i-1]+inp[i];
build(1,1,my_n);
for(int i=1;i<=my_n;i++)
{
while(1)
{
info cur=actual(tree[1]);
if(cur.mini)break;
int pos=cur.pos;
update(1,1,my_n,pos,pos,1e9);
add(pos);
}
/*
cout<<"i= "<<i<<endl;
cout<<"zeros= ";for(auto w:zeros)cout<<w<<" ";cout<<endl;
cout<<"legit= ";for(auto w:legit)cout<<w<<" ";cout<<endl;
*/
//cout<<"pos= "<<pos<<endl;
int pos=*legit.begin();
sub(pos);
outp[pos]=my_n-i;
int l=pos-(k-1);
int r=pos-1;
if(1<=l)update(1,1,my_n,l,r,-1);
else
{
l=l+my_n;
//cout<<"other "<<l<<" "<<my_n<<" and "<<1<<" "<<r<<endl;
update(1,1,my_n,l,my_n,-1);
if(r>=1)update(1,1,my_n,1,r,-1);
}
}
for(int i=1;i<=my_n;i++)outp[i+my_n]=outp[i];
//for(int i=1;i<=my_n;i++)printf("%i ",outp[i]);printf("\n");
build_merge(1,1,2*my_n);
for(int i=1;i<=my_n;i++)
{
go_right[0][i]=query(1,1,2*my_n,i+1,i+my_k-1,outp[i]);
if(go_right[0][i]==-1)go_right[0][my_n+i]=-1;
else go_right[0][my_n+i]=go_right[0][i]+my_n;
}
for(int i=my_n+1;i<=my_n+my_n;i++)
{
//cout<<"i= "<<i<<" : ";
go_left[0][i]=query(1,1,2*my_n,i-(my_k-1),i-1,outp[i-my_n]);
//cout<<"go_left= "<<go_left[i]<<endl;
if(go_left[0][i]==-1)go_left[0][i-my_n]=-1;
else go_left[0][i-my_n]=go_left[0][i]-my_n;
}
/*
cout<<"go_left: ";for(int i=1;i<=2*my_n;i++)cout<<go_left[i]<<" ";cout<<endl;
cout<<"go_right: ";for(int i=1;i<=2*my_n;i++)cout<<go_right[i]<<" ";cout<<endl;
*/
for(int step=1;step<20;step++)
{
for(int i=1;i<=2*my_n;i++)
{
int u=go_left[step-1][i];
if(u<0||u>2*my_n)go_left[step][i]=u;
else go_left[step][i]=go_left[step-1][u];
int v=go_right[step-1][i];
if(v<0||v>2*my_n)go_right[step][i]=v;
else go_right[step][i]=go_right[step-1][v];
}
}
}
int jump_right(int x,int RHS)
{
if(x>RHS)return x;
for(int i=19;i>=0;i--)
if(0<=go_right[i][x]&&go_right[i][x]<=RHS)x=go_right[i][x];
return go_right[0][x];
}
int jump_left(int x,int LHS)
{
if(x<LHS)return x;
for(int i=19;i>=0;i--)
if(0<=go_left[i][x]&&go_left[i][x]>=LHS)x=go_left[i][x];
return go_left[0][x];
}
int compare_plants(int x, int y) {
x++;
y++;
/*
int x_help=x;
while(x_help>=0&&x_help<=y-my_k)x_help=go_right[x_help];
if(x_help>=0&&outp[x_help]>=outp[y])return 1;
*/
int x_help=jump_right(x,y-my_k);
if(x_help>=0&&outp[x_help]>=outp[y])return 1;
/*
x_help=x+my_n;
while(x_help>=0&&x_help>=y+my_k)x_help=go_left[x_help];
if(x_help>=0&&outp[x_help]>=outp[y])return 1;
*/
x_help=jump_left(x+my_n,y+my_k);
if(x_help>=0&&outp[x_help]>=outp[y])return 1;
/*
int y_help=y;
while(y_help>=0&&y_help>=x+my_k)y_help=go_left[y_help];
if(y_help>=0&&outp[y_help]>=outp[x])return -1;
*/
int y_help=jump_left(y,x+my_k);
if(y_help>=0&&outp[y_help]>=outp[x])return -1;
/*
y_help=y;
while(y_help>=0&&y_help<=x+my_n-my_k)y_help=go_right[y_help];
if(y_help>=0&&outp[y_help]>=outp[x])return -1;
*/
y_help=jump_right(y,x+my_n-my_k);
if(y_help>=0&&outp[y_help]>=outp[x])return -1;
return 0;
}
/*
static int n, k, q;
static std::vector<int> r;
static std:: vector<int> x;
static std:: vector<int> y;
static std:: vector<int> answer;
int main() {
assert(scanf("%d%d%d", &n, &k, &q) == 3);
r.resize(n);
answer.resize(q);
for (int i = 0; i < n; i++) {
int value;
assert(scanf("%d", &value) == 1);
r[i] = value;
}
x.resize(q);
y.resize(q);
for (int i = 0; i < q; i++) {
assert(scanf("%d%d", &x[i], &y[i]) == 2);
}
fclose(stdin);
init(k, r);
for (int i = 0; i < q; i++) {
answer[i] = compare_plants(x[i], y[i]);
}
for (int i = 0; i < q; i++) {
printf("%d\n", answer[i]);
}
fclose(stdout);
return 0;
}
*/
