#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>k0, k1;
int K, n;
vector<int>A;
struct ST
{
int l, r;
pair<int, int> mn;
pair<int, int> mn1;
int del = 0;
int del1 = 0;
ST *left, *right;
ST(int l, int r, vector<int>&a): l(l), r(r)
{
if (l < r)
{
left = new ST(l, (l + r) / 2, a);
right = new ST((l + r) / 2 + 1, r, a);
mn = min(left->mn, right->mn);
}
else
mn = {a[l], l};
mn1 = mn;
}
void fix()
{
if (l == r)
{
mn.first += del;
del = 0;
}
else
{
mn.first += del;
left->del += del;
right->del += del;
del = 0;
}
}
void fix1()
{
if (l == r)
{
mn1.first += del1;
del1 = 0;
}
else
{
mn1.first += del1;
left->del1 += del1;
right->del1 += del1;
del1 = 0;
}
}
void add(int x, int y, int w)
{
if (x <= l && r <= y)
{
del += w;
return fix();
}
fix();
if (r < x || y < l)
return;
left->add(x, y, w);
right->add(x, y, w);
mn = min(left->mn, right->mn);
}
void add1(int x, int y, int w)
{
if (x <= l && r <= y)
{
del1 += w;
return fix1();
}
fix1();
if (r < x || y < l)
return;
left->add1(x, y, w);
right->add1(x, y, w);
mn1 = min(left->mn1, right->mn1);
}
};
int id[200000];
int N;
struct inter
{
int a, b;
inter() {}
inter(int x, int y)
{
a = x;
b = y;
}
bool contains(int c)
{
if (a <= c && c <= b)
return true;
if (a > b)
if (c >= a || c <= b)
return true;
return false;
}
};
inter merge(inter a, inter b)
{
if (a.a == -1)
return b;
if (b.a == -1)
return a;
if (a.a <= a.b && b.a <= b.b)
return inter({min(a.a, b.a), max(a.b, b.b)});
if (a.a < a.b && b.a < b.b)
{
int x = min(a.a, b.a);
int y = max(a.b, b.b);
if (x <= y) return inter(1, 0);
return inter(x, y);
}
if (a.a < a.b)
{
if (b.contains(a.a) || b.contains(a.a - 1))
{
int x = min(a.a, b.a);
if (x <= a.b)
return inter(1, 0);
return inter(x, a.b);
}
else
{
int y = max(a.b, b.b);
if (a.a <= y)
return inter(1, 0);
return inter(a.a, y);
}
}
}
struct ST1
{
int l, r;
inter xx;
ST1 *left, *right;
ST1(int l, int r): l(l), r(r)
{
if (l < r)
{
left = new ST1(l, (l + r) / 2);
right = new ST1((l + r) / 2 + 1, r);
}
xx = inter(l, r);
}
void set(int i, inter g)
{
if (l == r)
{
xx = g;
}
else
{
if (i <= (l + r) / 2)
left->set(i, g);
else
right->set(i, g);
xx = merge(left->xx, right->xx);
}
}
inter get(int x, int y)
{
if (x <= l && r <= y)
return xx;
if (y < l || r < x)
return inter(-1, -1);
return merge(left->get(x, y), right->get(x, y));
}
} mediss(0, 200000);
inter gett(int x, int y)
{
while (y >= n)
{
x -= n;
y -= n;
}
while (x < 0)
{
x += n;
y += n;
}
if (y < n)
{
return mediss.get(x, y);
}
else
{
return merge(mediss.get(x, n - 1), mediss.get(0, y - n));
}
}
void init(int k, vector<int> r)
{
K = k;
n = r.size();
N = n;
if (k == 2)
{
k0 = k1 = vector<int>(n, 0);
for (int t = 0; t < 2; t++)
for (int i = n - 1; i >= 0; i--)
{
if (r[i] == 0)
k0[i] = 1 + k0[(i + 1) % n];
else
k1[i] = 1 + k1[(i + 1) % n];
}
return;
}
if (2 * k > n)
{
ST medis(0, n - 1, r);
auto add = [&](int x, int y, int w)
{
while (y >= n)
{
x -= n;
y -= n;
}
while (x < 0)
{
x += n;
y += n;
}
if (y < n)
{
medis.add(x, y, w);
}
else
{
medis.add(x, n - 1, w);
medis.add(0, y - n, w);
}
};
auto add1 = [&](int x, int y, int w)
{
while (y >= n)
{
x -= n;
y -= n;
}
while (x < 0)
{
x += n;
y += n;
}
if (y < n)
{
medis.add1(x, y, w);
}
else
{
medis.add1(x, n - 1, w);
medis.add1(0, y - n, w);
}
};
while (medis.mn1.first == 0)
{
int i = medis.mn1.second;
add(i + 1, i + (k - 1), 1);
add1(i, i, 1);
}
A = vector<int>(n, -1);
for (int tt = 0; tt < n; tt++)
{
while (medis.mn1.first == 0)
{
int i = medis.mn1.second;
add(i + 1, i + (k - 1), 1);
add1(i, i, 1);
}
int i = medis.mn.second;
add(i + 1, i + (k - 1), -1);
add(i - (k - 1), i - 1, -1);
add1(i - (k - 1), i - 1, -1);
A[i] = tt;
add(i, i, n + 10000);
add1(i, i, n + 10000);
r[i] = n + 100;
}
return;
}
ST medis(0, n - 1, r);
auto add = [&](int x, int y, int w)
{
while (y >= n)
{
x -= n;
y -= n;
}
while (x < 0)
{
x += n;
y += n;
}
if (y < n)
{
medis.add(x, y, w);
}
else
{
medis.add(x, n - 1, w);
medis.add(0, y - n, w);
}
};
auto add1 = [&](int x, int y, int w)
{
while (y >= n)
{
x -= n;
y -= n;
}
while (x < 0)
{
x += n;
y += n;
}
if (y < n)
{
medis.add1(x, y, w);
}
else
{
medis.add1(x, n - 1, w);
medis.add1(0, y - n, w);
}
};
while (medis.mn1.first == 0)
{
int i = medis.mn1.second;
add(i + 1, i + (k - 1), 1);
add1(i, i, 1);
}
vector<int>K;
for (int tt = 0; tt < n; tt++)
{
while (medis.mn1.first == 0)
{
int i = medis.mn1.second;
add(i + 1, i + (k - 1), 1);
add1(i, i, 1);
}
int i = medis.mn.second;
add(i + 1, i + (k - 1), -1);
add(i - (k - 1), i - 1, -1);
add1(i - (k - 1), i - 1, -1);
add(i, i, n + 10000);
add1(i, i, n + 10000);
id[i] = tt;
K.push_back(i);
r[i] = n + 100;
}
reverse(K.begin(), K.end());
vector<int>ok;
for (int i : K)
{
mediss.set(i, gett(i - (k - 1), i + (k - 1)));
}
}
int compare_plants(int x, int y)
{
assert(x < y);
if (K == 2)
{
if (k0[x] >= y - x)
return 1;
if (k1[x] >= y - x)
return -1;
if (k0[y] >= n - y + x)
return -1;
if (k1[y] >= n - y + x)
return 1;
return 0;
}
if (!A.empty())
{
if (A[x] < A[y])
return 1;
else
return -1;
}
if (id[x] > id[y])
return -compare_plants(y, x);
if (mediss.get(x, x).contains(y))
return 1;
return 0;
}
