#include <bits/stdc++.h>
#include "plants.h"
using namespace std;
const int maxn = 1<<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);
//cout<<temp.first<<" keres first\n";
if(temp.first == 0)
return temp.second;
temp = keres(0, r, 1, 0, maxn);
//cout<<temp.first<<" keres second\n";
if(temp.first == 0)
return temp.second;
return -1;
}
pair<int, int> temp = keres(l, r, 1, 0, maxn);
//cout<<temp.first<<" keres one\n";
if(temp.first == 0)
return temp.second;
return -1;
}
struct node{
int l = -1, r = -1, lc, rc;
};
vector<node> g;
vector<int> vh;
int n;
void init(int k, std::vector<int> r) {
n = (int)r.size();
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);
}
//cout<<"x: "<<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);
}
/*cout<<"h: ";
for(int x : vh)
cout<<x<<" ";
cout<<"\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 += g[g[x].l].lc;
else
g[x].lc = 0;
if(g[x].r != -1)
g[x].rc += g[g[x].r].rc;
else
g[x].rc = 0;
}
/*for(int i = 0; i < n; i++)
cout<<"pont "<<i<<": "<<g[i].l<<" "<<g[i].r<<" | "<<g[i].lc<<" "<<g[i].rc<<"\n";*/
return;
}
bool benne(int l1, int r1, int l2, int r2){
return l1 <= l2 && r2 <= r1;
}
int compare_plants(int x, int y) {
int ret = 1;
if(vh[x] < vh[y]){
ret = -1;
swap(x, y);
}
int l1 = x - g[x].lc, r1 = x + g[x].rc, l2 = y - g[y].lc, r2 = y + g[y].rc;
if(benne(l1, r1, l2, r2) || benne(l1, r1, l2-n, r2-n) || benne(l1, r1, l2+n, r2+n))
return ret;
return 0;
}
