#include "plants.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <utility>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
using namespace std;
struct Node
{
pii mn, lazy;
}seg[808080];
void prop(int ind)
{
Node &x = seg[ind << 1], &y = seg[ind << 1 | 1], &nd = seg[ind];
if(nd.lazy.ff)
{
x.mn.ff += nd.lazy.ff;
y.mn.ff += nd.lazy.ff;
x.lazy.ff += nd.lazy.ff;
y.lazy.ff += nd.lazy.ff;
nd.lazy.ff = 0;
}
if(nd.lazy.ss)
{
x.mn.ss += nd.lazy.ss;
y.mn.ss += nd.lazy.ss;
x.lazy.ss += nd.lazy.ss;
y.lazy.ss += nd.lazy.ss;
nd.lazy.ss = 0;
}
}
void mrge(int ind)
{
seg[ind].mn = min(seg[ind << 1].mn, seg[ind << 1 | 1].mn);
}
void init_seg(vector<int> &r, int ind, int s, int e)
{
if(s + 1 == e)
{
seg[ind].mn = {r[s], 0};
seg[ind].lazy = {0, 0};
return;
}
int mid = s + e >> 1;
init_seg(r, ind << 1, s, mid);
init_seg(r, ind << 1 | 1, mid, e);
mrge(ind);
}
void upd1(int ind, int s, int e, int l, int r, int x)
{
if(e <= l || r <= s) return;
if(l <= s && e <= r)
{
seg[ind].mn.ff += x;
seg[ind].lazy.ff += x;
return;
}
prop(ind);
int mid = s + e >> 1;
upd1(ind << 1, s, mid, l, r, x);
upd1(ind << 1 | 1, mid, e, l, r, x);
mrge(ind);
}
void upd2(int ind, int s, int e, int l, int r, int x)
{
if(e <= l || r <= s) return;
if(l <= s && e <= r)
{
seg[ind].mn.ss += x;
seg[ind].lazy.ss += x;
return;
}
prop(ind);
int mid = s + e >> 1;
upd2(ind << 1, s, mid, l, r, x);
upd2(ind << 1 | 1, mid, e, l, r, x);
mrge(ind);
}
void qr1(vector<int> &ret, int ind, int s, int e, int l, int r)
{
if(e <= l || r <= s || seg[ind].mn.ff) return;
if(s + 1 == e)
{
ret.push_back(s);
return;
}
prop(ind);
int mid = s + e >> 1;
qr1(ret, ind << 1, s, mid, l, r);
qr1(ret, ind << 1 | 1, mid, e, l, r);
}
int qr2(int ind, int s, int e)
{
if(s + 1 == e) return s;
prop(ind);
int mid = s + e >> 1;
if(seg[ind << 1].mn == pii{0, 0}) return qr2(ind << 1, s, mid);
else return qr2(ind << 1 | 1, mid, e);
}
int N, K;
int ord[404040];
int rev[202020];
int ils[1616161];
int igr[1616161];
int sls[404040][20];
int sgr[404040][20];
void init3(int ind, int s, int e)
{
if(s + 1 == e)
{
ils[ind] = ord[s];
return;
}
int mid = s + e >> 1;
init3(ind << 1, s, mid);
init3(ind << 1 | 1, mid, e);
ils[ind] = max(ils[ind << 1], ils[ind << 1 | 1]);
}
void init4(int ind, int s, int e)
{
if(s + 1 == e)
{
igr[ind] = ord[s];
return;
}
int mid = s + e >> 1;
init4(ind << 1, s, mid);
init4(ind << 1 | 1, mid, e);
igr[ind] = min(igr[ind << 1], igr[ind << 1 | 1]);
}
void upd3(int ind, int s, int e, int l, int r, int x)
{
if(e <= l || r <= s || ils[ind] <= ord[x]) return;
if(s + 1 == e)
{
sls[s][0] = x;
ils[ind] = -1;
return;
}
int mid = s + e >> 1;
upd3(ind << 1, s, mid, l, r, x);
upd3(ind << 1 | 1, mid, e, l, r, x);
ils[ind] = max(ils[ind << 1], ils[ind << 1 | 1]);
}
void upd4(int ind, int s, int e, int l, int r, int x)
{
if(e <= l || r <= s || igr[ind] >= ord[x]) return;
if(s + 1 == e)
{
sgr[s][0] = x;
igr[ind] = (int)1e9;
return;
}
int mid = s + e >> 1;
upd4(ind << 1, s, mid, l, r, x);
upd4(ind << 1 | 1, mid, e, l, r, x);
igr[ind] = min(igr[ind << 1], igr[ind << 1 | 1]);
}
void init(int k, vector<int> r)
{
N = r.size(); K = k;
init_seg(r, 1, 0, N);
for(int i = 0; i <= N - K; ++i) if(!r[i]) upd2(1, 0, N, i + 1, i + K, 1);
for(int i = N - K + 1; i < N; ++i) if(!r[i]) upd2(1, 0, N, i + 1, N, 1), upd2(1, 0, N, 0, K - N + i, 1);
for(int i = 0; i < N; ++i)
{
int t = qr2(1, 0, N);
ord[t] = i;
vector<int> ls;
upd1(1, 0, N, t, t + 1, N);
if(t >= K - 1)
{
upd1(1, 0, N, t - K + 1, t, -1);
qr1(ls, 1, 0, N, t - K + 1, t);
}
else
{
upd1(1, 0, N, 0, t, -1);
upd1(1, 0, N, N - K + t + 1, N, -1);
qr1(ls, 1, 0, N, 0, t);
qr1(ls, 1, 0, N, N - K + t + 1, N);
}
if(t <= N - K) upd2(1, 0, N, t + 1, t + K, -1);
else
{
upd2(1, 0, N, t + 1, N, -1);
upd2(1, 0, N, 0, K - N + t, -1);
}
for(int j : ls)
{
if(j <= N - K) upd2(1, 0, N, j + 1, j + K, 1);
else
{
upd2(1, 0, N, j + 1, N, 1);
upd2(1, 0, N, 0, K - N + j, 1);
}
}
}
for(int i = 0; i < N; ++i) rev[ord[i]] = i;
for(int i = 0; i < N; ++i) ord[i + N] = ord[i];
init3(1, 0, 2 * N);
init4(1, 0, 2 * N);
for(int i = 0; i <= 2 * N; ++i) sls[i][0] = sgr[i][0] = 2 * N;
for(int i = N - 1; i >= 0; --i)
{
upd3(1, 0, 2 * N, rev[i] - K + 1, rev[i], rev[i]);
upd3(1, 0, 2 * N, rev[i] + N - K + 1, rev[i] + N, rev[i] + N);
}
for(int i = 0; i < N; ++i)
{
upd4(1, 0, 2 * N, rev[i] - K + 1, rev[i], rev[i]);
upd4(1, 0, 2 * N, rev[i] + N - K + 1, rev[i] + N, rev[i] + N);
}
for(int i = 1; i < 20; ++i) for(int j = 0; j <= 2 * N; ++j)
sls[j][i] = sls[sls[j][i - 1]][i - 1], sgr[j][i] = sgr[sgr[j][i - 1]][i - 1];
}
int compare_plants(int x, int y)
{
if(ord[x] < ord[y])
{
int tmp = x;
for(int i = 19; i >= 0; --i) if(sgr[tmp][i] + K - 1 < y) tmp = sgr[tmp][i];
if(tmp + K - 1 < y) tmp = sgr[tmp][0];
if(tmp != 2 * N && ord[tmp] < ord[y]) return 1;
tmp = y; x += N;
for(int i = 19; i >= 0; --i) if(sls[tmp][i] + K - 1 < x) tmp = sls[tmp][i];
if(tmp + K - 1 < x) tmp = sls[tmp][0];
if(tmp != 2 * N && ord[tmp] > ord[x]) return 1;
}
else
{
int tmp = x;
for(int i = 19; i >= 0; --i) if(sls[tmp][i] + K - 1 < y) tmp = sls[tmp][i];
if(tmp + K - 1 < y) tmp = sls[tmp][0];
if(tmp != 2 * N && ord[tmp] > ord[y]) return -1;
tmp = y; x += N;
for(int i = 19; i >= 0; --i) if(sgr[tmp][i] + K - 1 < x) tmp = sgr[tmp][i];
if(tmp + K - 1 < x) tmp = sgr[tmp][0];
if(tmp != 2 * N && ord[tmp] < ord[x]) return -1;
}
return 0;
}
