#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int pot = 262144;
constexpr int inf = 1e9 + 7;
class Tree{
public:
int b[pot * 2 + 7]; // - pot
int e[pot * 2 + 7]; // - pot
int mini[pot * 2 + 7];
int lazy[pot * 2 + 7]; // < 0
int lmo[pot * 2 + 7]; // if no 0 than -1 - pot
int rmo[pot * 2 + 7]; // if no 0 than -1 - pot
int cand[pot * 2 + 7]; // -1 <=> doesn't exist - pot
int k, n;
void quick_update(int w){
if (w >= pot)
return;
mini[w] = min(mini[w * 2], mini[w * 2 + 1]);
lmo[w] = (mini[w * 2] == 0 ? lmo[w * 2] : lmo[w * 2 + 1]);
rmo[w] = (mini[w * 2 + 1] == 0 ? rmo[w * 2 + 1] : rmo[w * 2]);
if (max(cand[w * 2], cand[w * 2 + 1]) != -1)
cand[w] = max(cand[w * 2], cand[w * 2 + 1]);
else
{
if (mini[w * 2 + 1] == 0 && (lmo[w * 2 + 1] - max(rmo[w * 2], b[w * 2] - 1) >= k))
cand[w] = lmo[w * 2 + 1];
else
cand[w] = -1;
}
if (w == 1 && cand[w] == -1)
cand[w] = lmo[w];
}
void newo(int w){
if (w >= pot){
lmo[w] = w - pot;
rmo[w] = w - pot;
return;
}
push_lazy(w * 2);
push_lazy(w * 2 + 1);
quick_update(w);
}
void push_lazy(int w){
if (lazy[w] == 0)
return;
if (w < pot){
mini[w * 2] += lazy[w];
lazy[w * 2] += lazy[w];
mini[w * 2 + 1] += lazy[w];
lazy[w * 2 + 1] += lazy[w];
}
lazy[w] = 0;
if (mini[w] == 0)
newo(w);
}
void init(int ck, vector <int> r){
k = ck;
n = (int)r.size();
for (int i = pot; i < pot * 2; i++) // bottom layer
{
b[i] = i - pot;
e[i] = i - pot;
mini[i] = (i - pot < n ? r[i - pot] : inf);
lazy[i] = 0;
lmo[i] = (mini[i] == 0 ? i - pot : -1);
rmo[i] = (mini[i] == 0 ? i - pot : -1);
cand[i] = -1;
}
for (int i = pot - 1; i > 0; i--)
{
b[i] = b[i * 2];
e[i] = e[i * 2 + 1];
lazy[i] = 0;
quick_update(i);
}
}
void sub(int bq, int eq, int w){
if (bq > e[w] || b[w] > eq)
return;
if (bq <= b[w] && e[w] <= eq){
mini[w]--;
lazy[w]--;
push_lazy(w);
return;
}
push_lazy(w);
sub(bq, eq, w * 2);
sub(bq, eq, w * 2 + 1);
quick_update(w);
}
void del(int bq, int eq, int w){
if (bq > e[w] || b[w] > eq)
return;
if (bq <= b[w] && e[w] <= eq){
mini[w] = inf;
lmo[w] = -1;
rmo[w] = -1;
cand[w] = -1;
lazy[w] = 0;
return;
}
push_lazy(w);
del(bq, eq, w * 2);
del(bq, eq, w * 2 + 1);
quick_update(w);
}
int get_big(){
int curr = cand[1];
del(curr, curr, 1);
if (curr - k + 1 >= 0)
sub(curr - k + 1, curr, 1);
else{
sub(0, curr, 1);
sub(n - k + curr + 1, n - 1, 1);
}
return curr;
}
};
int n;
Tree tree;
vector <int> h;
vector <int> lef[23], rig[23];
void debug(){
for (int i : lef[1])
cout << i << " ";
cout << "\n";
for (int i : rig[1])
cout << i << " ";
cout << "\n";
}
int conv(int a, int b){
return (a - b + n) % n;
}
void get_dag(int k)
{
lef[0].resize(n);
rig[0].resize(n);
set <pair <int, int> > sett; // h, id
for (int i = 1; i < k; i++)
sett.insert({h[i], i});
for (int i = 0; i < n; i++)
{
int j = (i + k) % n;
set <pair <int, int> >::iterator it;
it = sett.lower_bound(make_pair(h[i], i));
if (it == sett.begin())
rig[0][i] = -1;
else
rig[0][i] = prev(it)->second;
it = sett.lower_bound(make_pair(h[j], j));
if (it == sett.begin())
lef[0][j] = -1;
else
lef[0][j] = prev(it)->second;
// --------------------------------------------
sett.erase(make_pair(h[(i + 1) % n], (i + 1) % n));
sett.insert({h[j], j});
}
for (int step = 1; step <= 20; step++){
lef[step].resize(n);
rig[step].resize(n);
for (int i = 0; i < n; i++){
lef[step][i] = (lef[step - 1][i] > -1 ? lef[step - 1][lef[step - 1][i]] : -1);
rig[step][i] = (rig[step - 1][i] > -1 ? rig[step - 1][rig[step - 1][i]] : -1);
if (conv(lef[step - 1][i], i) < conv(lef[step][i], i))
lef[step][i] = -1;
if (conv(rig[step - 1][i], i) > conv(rig[step][i], i))
rig[step][i] = -1;
}
}
}
void init(int k, vector<int> r)
{
n = (int)r.size();
tree.init(k, r);
h.resize(n);
for (int i = n; i > 0; i--){
int curr = tree.get_big();
h[curr] = i;
}
get_dag(k);
//debug();
return;
}
bool is_path(int x, int y)
{
int xl = x;
for (int step = 20; step >= 0; step--){
if (lef[step][xl] > -1 && conv(lef[step][xl], x) >= conv(y, x))
xl = lef[step][xl];
}
if (xl == y)
return true;
if (lef[0][xl] > -1)
if (h[y] < h[xl])
return true;
int xr = x;
for (int step = 20; step >= 0; step--){
if (rig[step][xr] > -1 && conv(rig[step][xr], x) <= conv(y, x))
xr = rig[step][xr];
}
if (xr == y)
return true;
if (rig[0][xr] > -1)
if (h[y] < h[xr])
return true;
return false;
}
int compare_plants(int x, int y) {
if (is_path(x, y)){
return 1;
}
return -1;
/*if (is_path(y, x)){
return -1;
}
return 0;*/
}
