#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
int N;
bool sub1;
vector<int> esq, dir, id;
vector<pair<int, int> > mini;
vector<int> lz;
vector<int> R;
vector<pair<pair<int, int>, int> > seg;
vector<int> lz2;
void build(int pos, int ini, int fim){
lz[pos] = lz2[pos] = 0;
if(ini == fim){
mini[pos] = make_pair(R[ini], ini);
seg[pos] = make_pair(make_pair(1, 0), ini);
return;
}
int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
build(e, ini, mid);
build(d, mid + 1, fim);
mini[pos] = min(mini[e], mini[d]);
seg[pos] = min(seg[e], seg[d]);
}
void refresh2(int pos, int ini, int fim){
if(lz2[pos] == 0) return;
seg[pos].first.second += lz2[pos];
if(ini != fim){
int e = pos << 1, d = e | 1;
lz2[e] += lz2[pos];
lz2[d] += lz2[pos];
}
lz2[pos] = 0;
}
void activate(int pos, int ini, int fim, int id){
refresh2(pos, ini, fim);
if(ini > id || fim < id) return;
if(ini == fim){
seg[pos].first.first ^= 1;
refresh2(pos, ini, fim);
return;
}
int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
activate(e, ini, mid, id);
activate(d, mid + 1, fim, id);
seg[pos] = min(seg[e], seg[d]);
}
void update2(int pos, int ini, int fim, int p, int q, int val){
refresh2(pos, ini, fim);
if(ini > q || fim < p) return;
if(ini >= p && fim <= q){
lz2[pos] += val;
refresh2(pos, ini, fim);
return;
}
int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
update2(e, ini, mid, p, q, val);
update2(d, mid + 1, fim, p, q, val);
seg[pos] = min(seg[e], seg[d]);
}
void refresh(int pos, int ini, int fim){
if(lz[pos] == 0) return;
mini[pos].first += lz[pos];
if(ini != fim){
int e = pos << 1, d = e | 1;
lz[e] += lz[pos];
lz[d] += lz[pos];
}
lz[pos] = 0;
}
void update(int pos, int ini, int fim, int p, int q, int val){
refresh(pos, ini, fim);
if(ini > q || fim < p) return;
if(ini >= p && fim <= q){
lz[pos] += val;
refresh(pos, ini, fim);
return;
}
int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
update(e, ini, mid, p, q, val);
update(d, mid + 1, fim, p, q, val);
mini[pos] = min(mini[e], mini[d]);
}
void init(int k, vector<int> r) {
sub1 = k == 2;
R = r;
N = R.size();
if(sub1){
esq = vector<int> (N);
dir = vector<int> (N);
int ini;
for(ini = 0; ini < N; ini++)
if(r[ini] == 0) break;
ini++;
ini %= N;
esq[ini] = 0;
for(int i = ini + 1; i != ini; i++, i %= N){
int ant = i - 1;
if(ant < 0) ant += N;
esq[i] = esq[ant] + 1;
if(r[ant] == 0) esq[i] = 0;
}
for(ini = 0; ini < N; ini++)
if(r[ini] == 1) break;
dir[ini] = 0;
for(int i = (ini + N - 1) % N; i != ini; i += N - 1, i %= N){
int nex = i + 1;
if(nex >= N) nex -= N;
dir[i] = dir[nex] + 1;
if(r[i] == 1) dir[i] = 0;
}
return;
}
mini = vector<pair<int, int> > (4 * N);
seg = vector<pair<pair<int, int>, int> > (4 * N);
lz = lz2 = vector<int> (4 * N);
build(1, 0, N - 1);
id = vector<int> (N);
for(int i = 0; i < N; i++){
while(1){
int in = mini[1].first;
int idx = mini[1].second;
if(in != 0) break;
update(1, 0, N - 1, idx, idx, 1e8);
activate(1, 0, N - 1, idx);
update2(1, 0, N - 1, idx + 1, idx + k - 1, 1);
update2(1, 0, N - 1, 0, idx + k - 1 - N, 1);
}
int idx = seg[1].second;
update2(1, 0, N - 1, idx + 1, idx + k - 1, -1);
update2(1, 0, N - 1, 0, idx + k - 1 - N, -1);
activate(1, 0, N - 1, idx);
update(1, 0, N - 1, idx - k + 1, idx - 1, -1);
update(1, 0, N - 1, idx + N - k + 1, N - 1, -1);
id[idx] = N - i;
}
return;
}
int compare_plants(int x, int y) {
if(sub1){
if(x + dir[x] >= y) return 1;
if(x - esq[x] < 0 && (x + N - esq[x]) % N <= y) return 1;
if(y - esq[y] <= x) return -1;
if(y + dir[y] > N && (y + dir[y]) % N >= x) return -1;
return 0;
}
if(id[x] > id[y]) return 1;
else return -1;
return 0;
}
