#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
{
set<int>A;
inter() {}
void add(int i)
{
A.insert(i);
}
bool contains(int c)
{
if (A.count(c))
return true;
return false;
}
};
inter merge(const inter &a, const inter &b)
{
inter c = a;
for (int t : b.A)
c.add(t);
return c;
}
struct ST1
{
int l, r;
inter lazy;
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);
}
}
void fix()
{
if (l < r)
{
left->lazy = merge(left->lazy, lazy);
right->lazy = merge(right->lazy, lazy);
lazy = inter();
}
}
void add(int x, int y, inter g)
{
if (x <= l && r <= y)
{
lazy = merge(lazy, g);
return fix();
}
fix();
if (y < l || r < x)
return;
left->add(x, y, g);
right->add(x, y, g);
}
inter get(int x)
{
if (l == r)
return lazy;
fix();
if (x <= (l + r) / 2)
return left->get(x);
else
return right->get(x);
}
} mediss(0, 200000);
void adddd(int x, int y, inter c)
{
while (y >= n)
{
x -= n;
y -= n;
}
while (x < 0)
{
x += n;
y += n;
}
if (y < n)
{
return mediss.add(x, y, c);
}
else
{
mediss.add(x, n - 1, c);
mediss.add(0, y - n, c);
}
}
inter C[200000];
void init(int k, vector<int> r)
{
K = k;
n = r.size();
N = 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);
}
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)
{
inter c = mediss.get(i);
c.add(i);
C[i] = c;
adddd(i - (k - 1), i + (k - 1), c);
}
}
int compare_plants(int x, int y)
{
if (C[x].contains(y))
return 1;
if (C[y].contains(x))
return -1;
return 0;
}
