#pragma GCC optimize("Ofast")
#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef int ll;
namespace{
const ll mxN=2e5+5; // warning remember to build
const ll inf=1e9;
const ll LOG=21;
struct segtree{
vector<array<ll, 3>> tree;
vector<array<ll, 2>> lazy;
ll treelen;
void init(ll siz){
treelen=siz+1;
while(__builtin_popcount(treelen)!=1) treelen++;
tree=vector<array<ll, 3>> (2*treelen, {0, 0, 0});
lazy=vector<array<ll, 2>> (2*treelen, {0, 0});
}
void build(ll idx, ll low, ll high){
if(low==high) return;
ll mid=(low+high)/2;
build(2*idx, low, mid);
build(2*idx+1, mid+1, high);
tree[idx]=min(tree[2*idx], tree[2*idx+1]);
}
void push(ll idx, ll low, ll high){
for(ll i=2*idx;i<=2*idx+1;i++){
for(ll j=0;j<2;j++){
tree[i][j]+=lazy[idx][j];
lazy[i][j]+=lazy[idx][j];
}
}
lazy[idx][0]=0;
lazy[idx][1]=0;
}
void update1(ll idx, ll low, ll high, ll qlow, ll qhigh, ll id, ll val){
if(low>=qlow && high<=qhigh){
tree[idx][id]+=val;
lazy[idx][id]+=val;
return;
}
if(low>qhigh || high<qlow) return;
push(idx, low, high);
ll mid=(low+high)/2;
update1(2*idx, low, mid, qlow, qhigh, id, val);
update1(2*idx+1, mid+1, high, qlow, qhigh, id, val);
tree[idx]=min(tree[2*idx], tree[2*idx+1]);
}
void update(ll qlow, ll qhigh, ll id, ll val){
update1(1, 0, treelen-1, qlow, qhigh, id, val);
}
array<ll, 3> getmin1(ll idx, ll low, ll high, ll qlow, ll qhigh){
if(low>=qlow && high<=qhigh){
return tree[idx];
}
if(low>qhigh || high<qlow) return {inf, inf, inf};
push(idx, low, high);
ll mid=(low+high)/2;
return min(getmin1(2*idx, low, mid, qlow, qhigh),
getmin1(2*idx+1, mid+1, high, qlow, qhigh));
}
array<ll, 3> getmin(ll qlow, ll qhigh){
return getmin1(1, 0, treelen-1, qlow, qhigh);
}
ll bssmall(ll idx, ll low, ll high){
if(low==high) return low;
ll mid=(low+high)/2;
push(idx, low, high);
if(tree[2*idx][0]<=0){
return bssmall(2*idx, low, mid);
}
else{
return bssmall(2*idx+1, mid+1, high);
}
}
ll bsbig(ll idx, ll low, ll high, ll qlow, ll qhigh){
if(tree[idx][0]>0) return inf;
if(low>=qlow && high<=qhigh){
return bssmall(idx, low, high);
}
if(low>qhigh || high<qlow) return inf;
push(idx, low, high);
ll mid=(low+high)/2;
ll re=bsbig(2*idx, low, mid, qlow, qhigh);
if(re!=inf){
return re;
}
return bsbig(2*idx+1, mid+1, high, qlow, qhigh);
}
ll bs(ll qlow, ll qhigh){
return bsbig(1, 0, treelen-1, qlow, qhigh);
}
};
ll n, k;
vll adj[mxN];
// ll ans[mxN][mxN];
bool done[mxN];
ll val[2*mxN];
bool visited[mxN];
array<ll, 3> up[mxN][LOG], up2[mxN][LOG];
segtree seg;
void dfs(ll cur){
if(visited[cur]) return;
visited[cur]=1;
for(auto &it:adj[cur]){
dfs(it);
}
}
}
void init(int K, vector<int> a) {
n=a.size();
k=K;
seg.init(n);
for(ll i=0;i<n;i++){
seg.tree[i+seg.treelen]={a[i], 0, i};
}
seg.build(1, 0, seg.treelen-1);
auto add=[&](ll idx){
ll lef=(idx+1)%n;
ll rig=(idx+k-1)%n;
if(lef>rig){
seg.update(lef, n-1, 1, 1);
seg.update(0, rig, 1, 1);
}
else{
seg.update(lef, rig, 1, 1);
}
};
for(ll i=0;i<n;i++){
if(a[i]==0){
add(i);
}
}
for(ll i=n-1;i>=0;i--){
ll dumb=0;
array<ll, 3> tep=seg.getmin(0, n-1);
dumb=tep[2];
val[dumb]=i;
val[dumb+n]=i;
seg.update(dumb, dumb, 0, inf);
ll lef=(dumb+1)%n;
ll rig=(dumb+k-1)%n;
if(lef>rig){
seg.update(lef, n-1, 1, -1);
seg.update(0, rig, 1, -1);
}
else{
seg.update(lef, rig, 1, -1);
}
lef=(dumb-k+1+n)%n;
rig=(dumb-1+n)%n;
if(lef>rig){
seg.update(lef, n-1, 0, -1);
seg.update(0, rig, 0, -1);
ll pre=lef;
while(pre<=n-1){
ll good=seg.bs(pre, n-1);
if(good==inf) break;
add(good);
pre=good+1;
}
pre=0;
while(pre<=rig){
ll good=seg.bs(pre, rig);
if(good==inf) break;
add(good);
pre=good+1;
}
}
else{
seg.update(lef, rig, 0, -1);
ll pre=lef;
while(pre<=rig){
ll good=seg.bs(pre, rig);
if(good==inf) break;
add(good);
pre=good+1;
}
}
}
set<pll> st;
for(ll i=n-k+1;i<=n-1;i++){
st.insert({val[i], i});
}
for(ll i=0;i<n;i++){
auto it=st.lower_bound({val[i], i});
if(it==st.begin()){
up[i][0]={i, val[i], 0};
}
else{
pll tep=*prev(it);
ll nxt=tep.S;
up[i][0]={nxt, val[nxt], 0};
if(nxt>i){
up[i][0][2]++;
}
}
ll pid=(i-k+1+n)%n;
st.erase({val[pid], pid});
st.insert({val[i], i});
}
st.clear();
for(ll i=0;i<k-1;i++){
st.insert({val[i], i});
}
for(ll i=n-1;i>=0;i--){
auto it=st.lower_bound({val[i], i});
if(it==st.begin()){
up2[i][0]={i, val[i], 0};
}
else{
pll tep=*prev(it);
ll nxt=tep.S;
up2[i][0]={nxt, val[nxt], 0};
if(nxt<i){
up2[i][0][2]++;
}
}
ll pid=(i+k-1)%n;
st.erase({val[pid], pid});
st.insert({val[i], i});
}
for(ll j=1;j<LOG;j++){
for(ll i=0;i<n;i++){
ll nxt=up[i][j-1][0];
up[i][j][0]=up[nxt][j-1][0];
up[i][j][1]=up[nxt][j-1][1];
up[i][j][2]=up[i][j-1][2]+up[nxt][j-1][2];
}
}
for(ll j=1;j<LOG;j++){
for(ll i=0;i<n;i++){
ll nxt=up2[i][j-1][0];
up2[i][j][0]=up2[nxt][j-1][0];
up2[i][j][1]=up2[nxt][j-1][1];
up2[i][j][2]=up2[i][j-1][2]+up2[nxt][j-1][2];
}
}
}
int compare_plants(int x, int y) {
// if(2*k>n){
auto bsl=[&](ll cur, ll e){
ll sum=0;
for(ll i=LOG-1;i>=0;i--){
if(up[cur][i][1]>=e){
sum+=up[cur][i][2];
cur=up[cur][i][0];
}
}
array<ll, 2> re={cur, sum};
return re;
};
auto bsr=[&](ll cur, ll e){
ll sum=0;
for(ll i=LOG-1;i>=0;i--){
if(up2[cur][i][1]>=e){
sum+=up2[cur][i][2];
cur=up2[cur][i][0];
}
}
array<ll, 2> re={cur, sum};
return re;
};
if(val[x]>val[y]){
array<ll, 2> re=bsl(x, val[y]);
ll dumb=0;
if(y>x) dumb++;
if(re[1]>dumb){
return 1;
}
else if(re[1]==dumb && re[0]<=y){
return 1;
}
re=bsr(x, val[y]);
dumb=0;
if(y<x) dumb++;
if(re[1]>dumb){
return 1;
}
else if(re[1]==dumb && re[0]>=y){
return 1;
}
return 0;
}
else{
array<ll, 2> re=bsl(y, val[x]);
ll dumb=0;
if(x>y) dumb++;
if(re[1]>dumb){
return -1;
}
else if(re[1]==dumb && re[0]<=x){
return -1;
}
re=bsr(y, val[x]);
dumb=0;
if(x<y) dumb++;
if(re[1]>dumb){
return -1;
}
else if(re[1]==dumb && re[0]>=x){
return -1;
}
return 0;
}
// }
// return (int) ans[x][y];
}
