#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;
int n, k;
vector<int> dpL, dpR;
void init_k2(vector<int> r){
dpL.resize(n), dpR.resize(n);
for(int it = 0; it < 2; it++){
for(int i = n-1; i >= 0; i--){
if(r[i]) dpR[i] = dpR[(i+1)%n]+1;
}
for(int i = 0; i < n; i++){
if(!r[(i+n-1)%n]) dpL[i] = dpL[(i+n-1)%n]+1;
}
}
}
struct Data{
int m = INF, l, r, ind = -1;
};
Data combine(Data a, Data b){
Data d;
d.m = min(a.m, b.m);
if(d.m == a.m) d.l = a.l;
else d.l = b.l;
if(d.m == b.m) d.r = b.r;
else d.r = a.r;
if(d.m == a.m && a.ind != -1) d.ind = a.ind;
if(d.m == b.m && b.ind != -1) d.ind = b.ind;
if(d.m == a.m && d.m == b.m && b.l-a.r >= k) d.ind = b.l;
return d;
}
int cap;
vector<Data> S;
vector<int> O;
vector<bool> lazy;
void build(vector<int> v){
for(cap = 1; cap < (int)v.size(); cap *= 2);
S.resize(2*cap);
O.resize(2*cap);
lazy.resize(2*cap);
for(int i = 0; i < (int)v.size(); i++) S[i+cap] = Data{v[i], i+1, i+1};
for(int i = cap-1; i > 0; i--) S[i] = combine(S[2*i], S[2*i+1]);
}
void apply(int v, int i){
lazy[i] = true;
O[i] += v;
S[i].m += v;
}
void push(int i){
if(lazy[i]){
apply(O[i], 2*i);
apply(O[i], 2*i+1);
O[i] = 0;
lazy[i] = false;
}
}
void upd(int p, int v, int a, int b, int i){
if(a == b) S[i] = {v, p, p, -1};
else{
push(i);
int m = (a+b)/2;
if(p <= m) upd(p, v, a, m, 2*i);
else upd(p, v, m+1, b, 2*i+1);
S[i] = combine(S[2*i], S[2*i+1]);
}
}
void apply(int l, int r, int v, int a, int b, int i){
if(l <= a && b <= r) apply(v, i);
else if(b < l || r < a) return;
else{
push(i);
int m = (a+b)/2;
apply(l, r, v, a, m, 2*i);
apply(l, r, v, m+1, b, 2*i+1);
S[i] = combine(S[2*i], S[2*i+1]);
}
}
vector<int> h;
void init_else(vector<int> r){
h.resize(2*n);
r.resize(2*n);
for(int i = 0; i < n; i++) r[i+n] = r[i];
build(r);
for(int it = 0; it < n; it++){
assert(S[1].m == 0);
assert(S[1].ind != -1);
int i = S[1].ind;
i = (i-1)%n;
h[i] = h[i+n] = n-it;
upd(i+1, INF, 1, cap, 1);
upd(i+n+1, INF, 1, cap, 1);
apply(max(0, i-k+1)+1, i, -1, 1, cap, 1);
apply(i+n-k+2, i+n, -1, 1, cap, 1);
apply(i+2*n-k+2, 2*n, -1, 1, cap, 1);
}
}
void init(int K, vector<int> r) {
k = K;
n = (int)r.size();
if(k == 2) init_k2(r);
else init_else(r);
}
int compare_k2(int x, int y){
int d1 = (y-x+n)%n;
int d2 = n-d1;
if(dpR[x] >= d1 || dpL[x] >= d2) return -1;
if(dpR[y] >= d2 || dpL[y] >= d1) return 1;
return 0;
}
int compare_else(int x, int y){
if(h[x] < h[y]) return -1;
else return 1;
}
int compare_plants(int x, int y) {
if(k == 2) return compare_k2(x, y);
else return compare_else(x, y);
}
