#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,k,R[200009],cnt,f[200009],seg[800009],seg2[800009],segmn[800009],za,l,r,z,zz,ll,rr,RE[200009];
int rg[200009][20],lf[200009][20];
set <int> s;
set <int>::iterator it,tt;
set <pair <int, int> > st;
set <pair <int, int> >::iterator IT;
void pushdown(int q, int w, int rr){
if(q!=w){
seg2[rr*2]+=seg2[rr];
seg2[rr*2+1]+=seg2[rr];
}
segmn[rr]+=seg2[rr];
seg2[rr]=0;
}
void upd(int q, int w, int rr){
pushdown(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
seg2[rr]+=z;
pushdown(q,w,rr);
return;
}
upd(q,(q+w)/2,rr*2);
upd((q+w)/2+1,w,rr*2+1);
if(segmn[rr*2]<segmn[rr*2+1]){
seg[rr]=seg[rr*2];segmn[rr]=segmn[rr*2];
}
if(segmn[rr*2]>segmn[rr*2+1]){
seg[rr]=seg[rr*2+1];segmn[rr]=segmn[rr*2+1];
}
if(segmn[rr*2]==segmn[rr*2+1]){
segmn[rr]=segmn[rr*2+1];
seg[rr]=min(seg[rr*2],seg[rr*2+1]);
}
}
void UPD(int q, int w, int rr){
l=q+1;r=w+1;z=rr;
upd(1,za,1);
}
void read(int q, int w, int rr){
pushdown(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
if(z>segmn[rr]){
z=segmn[rr];zz=seg[rr];
}else{
if(z==segmn[rr]){
if(zz>seg[rr]) zz=seg[rr];
}
}
return;
}
read(q,(q+w)/2,rr*2);
read((q+w)/2+1,w,rr*2+1);
}
void READ(int q, int w){
q++;w++;
while(q<=w){
l=q;r=w;z=a+3;zz=a+3;
read(1,za,1);
if(z!=0||zz>w) break;
zz--;
it=s.lower_bound(zz);
if(it==s.end()) it=s.begin();
if(it!=s.begin()){
tt=it;tt--;
}else{
tt=s.end();tt--;
}
st.erase(st.lower_bound(make_pair(((*it)+a-(*tt))%a,(*it))));
st.insert(make_pair(((*it)+a-zz)%a,(*it)));
st.insert(make_pair((zz+a-(*tt))%a,zz));
s.insert(zz);
zz++;
q=zz+1;
}
}
void init(int Kk, vector<int> Rr) {
a=Rr.size();k=Kk-1;
for(i=0; i<a; i++){
R[i]=Rr[i];
}
za=1;
while(za<a) za*=2;
for(i=0; i<a; i++){
seg[za+i]=i+1;segmn[za+i]=R[i];
if(R[i]==0){
s.insert(i);
}
}
for(i=za-1; i>=1; i--){
if(segmn[i*2]<segmn[i*2+1]){
seg[i]=seg[i*2];segmn[i]=segmn[i*2];
}
if(segmn[i*2]>segmn[i*2+1]){
seg[i]=seg[i*2+1];segmn[i]=segmn[i*2+1];
}
if(segmn[i*2]==segmn[i*2+1]){
segmn[i]=segmn[i*2+1];
seg[i]=min(seg[i*2],seg[i*2+1]);
}
}
for(it=s.begin(); it!=s.end(); it++){
tt=it;tt++;
if(tt==s.end()) tt=s.begin();
st.insert(make_pair(((*tt)+a-(*it))%a,(*tt)));
}
cnt=a;
while(cnt>0){
IT=st.end();IT--;
i=(*IT).second;
f[i]=cnt;cnt--;
if(cnt==0) break;
if(i-k>=0){
UPD(i-k,i-1,-1);
READ(i-k,i-1);
}else{
UPD(0,i-1,-1);
UPD(a-(k-i),a-1,-1);
READ(0,i-1);
READ(a-(k-i),a-1);
}
s.erase(s.lower_bound(i));
it=s.lower_bound(i);
if(it==s.end()) it=s.begin();
if(it!=s.begin()){
tt=it;tt--;
}else{
tt=s.end();tt--;
}
st.erase(st.lower_bound(make_pair(((*it)+a-i)%a,(*it))));
st.erase(st.lower_bound(make_pair((i+a-(*tt))%a,i)));
st.insert(make_pair(((*it)+a-(*tt))%a,(*it)));
l=i+1;r=i+1;z=a+3;
upd(1,za,1);
}
st.clear();
for(j=0; j<k; j++){
st.insert(make_pair(f[j],j));
}
for(i=0; i<a; i++){
st.erase(st.lower_bound(make_pair(f[i],i)));
st.insert(make_pair(f[(i+k)%a],(i+k)%a));
IT=st.lower_bound(make_pair(f[i],0));
if(IT==st.begin()){
rg[i][0]=-1;
}else{
IT--;
rg[i][0]=(*IT).second;
}
}
st.clear();
for(j=a-1; j>=a-k; j--){
st.insert(make_pair(f[j],j));
}
for(i=a-1; i>=0; i--){
st.erase(st.lower_bound(make_pair(f[i],i)));
st.insert(make_pair(f[(i+a-k)%a],(i+a-k)%a));
IT=st.lower_bound(make_pair(f[i],0));
if(IT==st.begin()){
lf[i][0]=-1;
}else{
IT--;
lf[i][0]=(*IT).second;
}
}
for(j=1; j<=18; j++){
for(i=0; i<a; i++){
if(rg[i][j-1]==-1){
rg[i][j]=-1;
continue;
}
zx=rg[rg[i][j-1]][j-1];
if(zx==-1){
rg[i][j]=-1;
continue;
}
if(i<=zx){
l=i;r=zx;
ll=l;rr=r;
}else{
l=i;r=a-1;
ll=0;rr=zx;
}
if((l<=rg[i][j-1]&&rg[i][j-1]<=r)||(ll<=rg[i][j-1]&&rg[i][j-1]<=rr)){
rg[i][j]=zx;
}else{
rg[i][j]=-1;
continue;
}
}
}
for(j=1; j<=18; j++){
for(i=0; i<a; i++){
if(lf[i][j-1]==-1){
lf[i][j]=-1;
continue;
}
zx=lf[lf[i][j-1]][j-1];
if(zx==-1){
lf[i][j]=-1;
continue;
}
if(i>=zx){
l=zx;r=i;
ll=l;rr=r;
}else{
l=zx;r=a-1;
ll=0;rr=i;
}
if((l<=lf[i][j-1]&&lf[i][j-1]<=r)||(ll<=lf[i][j-1]&&lf[i][j-1]<=rr)){
lf[i][j]=zx;
}else{
lf[i][j]=-1;
continue;
}
}
}
return;
}
int compare_plants(int x, int y) {
c=x;d=y;
for(j=18; j>=0; j--){
if(c<=d){
l=c;r=d;
ll=l;rr=r;
}else{
l=c;r=a-1;
ll=0;rr=d;
}
if(rg[c][j]==-1) continue;
if((l<=rg[c][j]&&rg[c][j]<=r)||(ll<=rg[c][j]&&rg[c][j]<=rr)){
c=rg[c][j];
}
}
if((d+a-c)%a<=k&&f[c]>=f[d]){
return 1;
}
c=x;d=y;
for(j=18; j>=0; j--){
if(c>=d){
l=d;r=c;
ll=l;rr=r;
}else{
l=d;r=a-1;
ll=0;rr=c;
}
if(lf[c][j]==-1) continue;
if((l<=lf[c][j]&&lf[c][j]<=r)||(ll<=lf[c][j]&&lf[c][j]<=rr)){
c=lf[c][j];
}
}
if((c+a-d)%a<=k&&f[c]>=f[d]){
return 1;
}
c=y;d=x;
for(j=18; j>=0; j--){
if(c<=d){
l=c;r=d;
ll=l;rr=r;
}else{
l=c;r=a-1;
ll=0;rr=d;
}
if(rg[c][j]==-1) continue;
if((l<=rg[c][j]&&rg[c][j]<=r)||(ll<=rg[c][j]&&rg[c][j]<=rr)){
c=rg[c][j];
}
}
if((d+a-c)%a<=k&&f[c]>=f[d]){
return -1;
}
c=y;d=x;
for(j=18; j>=0; j--){
if(c>=d){
l=d;r=c;
ll=l;rr=r;
}else{
l=d;r=a-1;
ll=0;rr=c;
}
if(lf[c][j]==-1) continue;
if((l<=lf[c][j]&&lf[c][j]<=r)||(ll<=lf[c][j]&&lf[c][j]<=rr)){
c=lf[c][j];
}
}
if((c+a-d)%a<=k&&f[c]>=f[d]){
return -1;
}
return 0;
}
