#include "plants.h"
#include <queue>
#include <bitset>
template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}
template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}
const int MN = 2e5+10;
const int INF = 0x3f3f3f3f;
int N, K, ctr, ord[MN];
bool v[MN];
//Minmax Segtree
struct minmax
{
public:
int min, max;
minmax(int _mn=INF, int _mx=-INF): min(_mn), max(_mx) {}
minmax& operator += (const int& o) {min += o, max += o; return *this;}
minmax& operator -= (const int& o) {min -= o, max -= o; return *this;}
minmax& operator += (const minmax& o) {ckmin(min, o.min); ckmax(max, o.max); return *this;}
friend minmax operator + (minmax a, const int& b) {return a+=b;}
friend minmax operator - (minmax a, const int& b) {return a-=b;}
friend minmax operator + (minmax a, const minmax& b) {return a+=b;}
bool contains(int x) {return min <= x && x <= max;}
} range[MN];
minmax mv[1 << 19];
minmax mqry(int n, int l, int r, int ql, int qr)
{
if(ql <= l && r <= qr) return mv[n];
else
{
int m=l+(r-l)/2; minmax f;
if(ql < m) f += mqry(n<<1, l, m, ql, qr);
if(m < qr) f += mqry(n<<1|1, m, r, ql, qr);
return r;
}
}
void mupd(int n, int l, int r, int q, minmax val)
{
if(r-l>1)
{
int m=l+(r-l)/2;
if(q < m) mupd(n<<1, l, m, q, val);
else mupd(n<<1|1, m, r, q, val);
mv[n]=mv[n<<1]+mv[n<<1|1];
}
else
mv[n]=val;
}
void init(int k, std::vector<int> r) {
K=k, N=r.size();
std::queue<int> q;
int zc=0;
for(int i=N-K;i<N;++i)
zc += !r[i];
for(int i=0;i<N;++i)
{
zc -= !r[(N-K+i)%N];
if(zc==0 && r[i]==0)
q.push(i);
zc += !r[i];
}
for(;!q.empty();)
{
int n=q.front(); q.pop();
if(r[n] < 0) continue;
// check
bool ok=1;
for(int i=1;i<K;++i)
if(r[(n-i+N)%N]==0)
ok=0;
if(!ok) continue;
// add
r[n]=-1;
for(int i=K-1;i>0;--i)
--r[(n-i+N)%N];
for(int i=1;i<K;++i)
if(r[(n+i)%N] == 0)
{
q.push((n+i)%N);
break;
}
for(int i=K-1;i>0;--i)
if(r[(n-i+N)%N] == 0)
{
q.push((n-i+N)%N);
break;
}
//modify ans
ord[n]=ctr++;
range[n] = minmax(n-K+1, n+K-1);
range[n] += mqry(1, 0, N, n-K+1, n+K);
if(n+K>N) range[n] += mqry(1, 0, N, 0, n+K-N)+N;
if(n-K+1<0) range[n] += mqry(1, 0, N, n-K+1+N, N)-N;
mupd(1, 0, N, n, range[n]);
//printf("%d: %d <-> %d\n", n, range[n].min, range[n].max);
}
return;
}
bool cover(int a, int b) // is a < b?
{
if(ord[a]<ord[b]) return 0;
return range[a].contains(b) || range[a].contains(b+N) || range[a].contains(b-N);
}
int compare_plants(int x, int y)
{
if(cover(x, y)) return -1;
if(cover(y, x)) return 1;
return 0;
}
