#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[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];
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++)printf("%i ",outp[i]);printf("\n");
}
int compare_plants(int x, int y) {
x++;
y++;
if(my_k==2)
{
if(pref[y-1]-pref[x-1]==y-x)return -1;
if(pref[y-1]-pref[x-1]==0)return 1;
if(pref[x-1]+pref[my_n]-pref[y-1]==my_n-y+x)return 1;
if(pref[x-1]+pref[my_n]-pref[y-1]==0)return -1;
return 0;
}
if(outp[x]>outp[y])return 1;
return -1;
}
/*
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;
}
*/
