#include <bits/stdc++.h>
#include "plants.h"
using namespace std;
const int maxn = 1<<18, logn = 18;
pair<int, int> st[maxn<<1];
int add[maxn<<1] = {};
void prop(int x){
if(x < maxn){
add[2*x] += add[x];
st[2*x].first += add[x];
add[2*x+1] += add[x];
st[2*x+1].first += add[x];
}
add[x] = 0;
}
inline void upd(int &x){
if(x < maxn) st[x] = min(st[2*x], st[2*x+1]);
}
void build(vector<int> &v){
for(int i = 0; i < (int)v.size(); i++)
st[maxn+i] = make_pair(v[i], i);
for(int i = maxn-1; i > 0; i--)
upd(i);
}
void kivesz(int ind, int x, int l, int r){
prop(x);
if(l+1 == r){
st[x].first = (int)1e9;
return;
}
int m = (l+r)/2;
if(ind < m)
kivesz(ind, 2*x, l, m);
else
kivesz(ind, 2*x+1, m, r);
upd(x);
}
void update(int s, int e, int x, int l, int r){
prop(x);
if(e <= l || r <= s)
return;
if(s <= l && r <= e){
st[x].first--;
add[x]--;
return;
}
int m = (l+r)/2;
update(s, e, 2*x, l, m);
update(s, e, 2*x+1, m, r);
upd(x);
}
void update(int l, int r, int n){
if(l > r){
update(l, n, 1, 0, maxn);
update(0, r, 1, 0, maxn);
} else
update(l, r, 1, 0, maxn);
}
pair<int, int> keres(int s, int e, int x, int l, int r){
prop(x);
if(e <= l || r <= s)
return make_pair((int)1e9, 0);
if(s <= l && r <= e)
return st[x];
int m = (l+r)/2;
return min(keres(s, e, 2*x, l, m), keres(s, e, 2*x+1, m, r));
}
int keres(int l, int r, int n){
if(r < l){
pair<int, int> temp = keres(l, n, 1, 0, maxn);
if(temp.first == 0)
return temp.second;
temp = keres(0, r, 1, 0, maxn);
if(temp.first == 0)
return temp.second;
return -1;
}
pair<int, int> temp = keres(l, r, 1, 0, maxn);
if(temp.first == 0)
return temp.second;
return -1;
}
struct node{
int l = -1, r = -1;
long long lc, rc;
vector<int> indL, indR;
vector<long long> hL, hR;
};
vector<node> g;
vector<int> vh;
int n, K;
void init(int k, std::vector<int> r) {
n = (int)r.size();
K = k;
g.resize(n);
vh.resize(n);
for(int &x : r)
x = k-x-1;
build(r);
int x = keres(0, n, n), h = 0;
vector<int> sor;
while(x != -1){
int y = keres((x-k+1 < 0 ? n+x-k+1 : x-k+1), x, n);
while(y != -1){
x = y;
y = keres((x-k+1 < 0 ? n+x-k+1 : x-k+1), x, n);
}
vh[x] = h++;
sor.push_back(x);
update((x-k+1 < 0 ? n+x-k+1 : x-k+1), x, n);
kivesz(x, 1, 0, maxn);
x = keres(x+1, x, n);
}
set<pair<int, int>, greater<pair<int, int>>> nums;
for(int i = n-k+1; i < n; i++)
nums.insert(make_pair(vh[i], i));
for(int i = 0; i < n; i++){
auto it = nums.lower_bound(make_pair(vh[i], i));
if(it != nums.end())
g[i].l = it->second;
int j = i-k+1;
if(j < 0) j += n;
nums.erase(make_pair(vh[j], j));
nums.insert(make_pair(vh[i], i));
}
nums.clear();
for(int i = 0; i < k-1; i++)
nums.insert(make_pair(vh[i], i));
for(int i = n-1; i >= 0; i--){
auto it = nums.lower_bound(make_pair(vh[i], i));
if(it != nums.end())
g[i].r = it->second;
int j = i+k-1;
if(j >= n) j -= n;
nums.erase(make_pair(vh[j], j));
nums.insert(make_pair(vh[i], i));
}
for(int x : sor){
g[x].lc = x - g[x].l;
if(g[x].lc < 0) g[x].lc += n;
g[x].rc = g[x].r - x;
if(g[x].rc < 0) g[x].rc += n;
if(g[x].l == -1)
g[x].lc = 0;
if(g[x].r == -1)
g[x].rc = 0;
g[x].indL.assign(logn, -1);
g[x].indR.assign(logn, -1);
g[x].hL.assign(logn, (long long)1e9);
g[x].hR.assign(logn, (long long)1e9);
g[x].indL[0] = g[x].l;
g[x].hL[0] = (g[x].l == -1 ? (long long)1e9 : g[x].lc);
g[x].indR[0] = g[x].r;
g[x].hR[0] = (g[x].r == -1 ? (long long)1e9 : g[x].rc);
for(int i = 1; i < logn; i++){
if(g[x].indL[i-1] == -1)
break;
g[x].indL[i] = g[g[x].indL[i-1]].indL[i-1];
if(g[x].indL[i] != -1)
g[x].hL[i] = g[x].hL[i-1] + g[g[x].indL[i-1]].hL[i-1];
}
for(int i = 1; i < logn; i++){
if(g[x].indR[i-1] == -1)
break;
g[x].indR[i] = g[g[x].indR[i-1]].indR[i-1];
if(g[x].indR[i] != -1)
g[x].hR[i] = g[x].hR[i-1] + g[g[x].indR[i-1]].hR[i-1];
}
}
/*cout<<"vh: ";
for(int x : vh)
cout<<x<<" ";
cout<<"\n";
for(int i = 0; i < n; i++){
cout<<"pont "<<i<<": "<<g[i].l<<" "<<g[i].r<<" | "<<g[i].lc<<" "<<g[i].rc<<"\n";
cout<<"inds: ";
for(int x : g[i].indL)
cout<<x<<" ";
cout<<"\n";
cout<<"h: ";
for(int x : g[i].hL)
cout<<x<<" ";
cout<<"\n";
}*/
return;
}
int compare_plants(int x, int y) {
int ret = 1;
if(vh[x] < vh[y]){
ret = -1;
swap(x, y);
}
long long d = x-y;
if(d < 0) d += n;
int a = x;
for(int i = logn-1; i >= 0; i--){
if(d >= g[a].hL[i]){
d -= g[a].hL[i];
a = g[a].indL[i];
}
}
if(d < K && vh[a] >= vh[y])
return ret;
d = y-x;
if(d < 0) d += n;
//cout<<"disR: "<<d<<"\n";
a = x;
for(int i = logn-1; i >= 0; i--){
if(d >= g[a].hR[i]){
d -= g[a].hR[i];
a = g[a].indR[i];
}
}
//cout<<a<<" a\n";
if(d < K && vh[a] >= vh[y])
return ret;
return 0;
}
