#include "plants.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
int N;
int K;
const long long INF = 1e9;
struct segtree
{
int l;
int r;
pair<long long, int> mn; //min first, index second
pair<long long, int> mx; //max first, index second
int lp = 0;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
mn = make_pair(0, l);
mx = make_pair(0, l);
if(l == r) return;
int m = (l+r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
}
void add(int L, int R, long long V)
{
L = (L + 10*N) % N;
R = (R + 10*N) % N;
if(R < L)
{
add(L, N-1, V);
add(0, R, V);
return;
}
if(R < l || r < L) return;
else if(L <= l && r <= R)
{
lp += V;
mn.first += V;
mx.first += V;
}
else
{
left->add(L, R, V);
right->add(L, R, V);
mn = min(left->mn, right->mn);
mn.first += lp;
mx = max(left->mx, right->mx);
mx.first += lp;
}
}
pair<long long, int> rangemin(int L, int R)
{
L = (L + 10*N) % N;
R = (R + 10*N) % N;
if(R < L)
{
return min(rangemin(L, N-1), rangemin(0, R));
}
if(R < l || r < L) return make_pair(+2*INF, -1);
else if(L <= l && r <= R)
{
return mn;
}
else
{
pair<long long, int> A = min(left->rangemin(L, R), right->rangemin(L, R));
A.first += lp;
return A;
}
}
pair<long long, int> rangemax(int L, int R)
{
L = (L + 10*N) % N;
R = (R + 10*N) % N;
if(R < L)
{
return max(rangemax(L, N-1), rangemax(0, R));
}
if(R < l || r < L) return make_pair(-2*INF, -1);
else if(L <= l && r <= R)
{
return mx;
}
else
{
pair<long long, int> A = max(left->rangemax(L, R), right->rangemax(L, R));
A.first += lp;
// cerr << "returning " << A.first << ' ' << A.second << " for rangemax " << L << ' ' << R << '\n';
return A;
}
}
};
segtree R;
vector<int> pos;
int dist(int x, int y) //clockwise distance from x to y
{
x = x % N;
y = y % N;
if(y < x) y += N;
return y-x;
}
const int maxN = 200'000;
const int lgN = 18;
int right_high[maxN][lgN];
int left_high[maxN][lgN];
int right_low[maxN][lgN];
int left_low[maxN][lgN];
vector<int> H;
void init(int k, vector<int> r)
{
N = r.size();
K = k;
segtree R(0, N-1);
segtree S(0, N-1);
for(int i = 0; i < N; i++)
{
R.add(i, i, +r[i]);
if(r[i] >= 1)
S.add(i+1, i+K-1, +1);
if(r[i] != 0)
S.add(i, i, -INF);
}
vector<int> inv_h_order;
for(int t = 0; t < N; t++)
{
pair<long long, int> p = S.rangemax(0, N-1);
int I = p.second;
inv_h_order.push_back(I);
// cerr << "I = " << I << '\n';
R.add(I, I, +INF);
S.add(I, I, -INF);
S.add(I+1, I+K-1, +1);
vector<int> newzeros;
// R.add(I+1, I+K-1, -1);
R.add(I-K+1, I-1, -1);
while(1)
{
// for(int i = 0; i < N; i++) cerr << R.rangemin(i, i).second << ' ';
// cerr << '\n';
pair<long long, int> q = R.rangemin(I-K+1, I-1);
if(q.first > 0) break;
// cerr << "q = " << q.second << '\n';
newzeros.push_back(q.second);
R.add(q.second, q.second, +1);
}
for(int z: newzeros)
{
R.add(z, z, -1);
S.add(z, z, +INF);
}
for(int z: newzeros)
S.add(z+1, z+K-1, -1);
}
vector<int> h(N);
for(int i = 0; i < N; i++) h[ inv_h_order[i] ] = N-1 - i;
pos = vector<int>(N);
for(int i = 0; i < N; i++)
pos[ h[i] ] = i;
segtree HT(0, N-1);
for(int i = 0; i < N; i++) HT.add(i, i, h[i] + INF);
for(int u = N-1; u >= 0; u--)
{
//right
pair<long long, int> z = HT.rangemin(pos[u]+1, pos[u]+K-1);
if(z.first >= INF)
right_high[pos[u]][0] = pos[u];
else
right_high[pos[u]][0] = z.second;
z = HT.rangemin(pos[u]-K+1, pos[u]-1);
if(z.first >= INF)
left_high[pos[u]][0] = pos[u];
else
left_high[pos[u]][0] = z.second;
HT.add(pos[u], pos[u], -INF);
}
for(int e = 1; e < lgN; e++)
{
for(int i = 0; i < N; i++)
{
right_high[i][e] = right_high[ right_high[i][e-1] ][e-1];
left_high[i][e] = left_high[ left_high[i][e-1] ][e-1];
}
}
H = h;
// for(int i = 0; i < N; i++) cerr << H[i] << ' ';
// cerr << '\n';
// for(int i = 0; i < N; i++) cerr << left_high[i][0] << ' ';
// cerr << '\n';
// for(int i = 0; i < N; i++) cerr << right_high[i][0] << ' ';
// cerr << '\n';
}
bool query_right(int x, int y)
{
if(dist(x, y) < K || dist(y, x) < K)
{
return H[x] < H[y];
}
for(int e = lgN - 1; e >= 0; e--)
{
if(H[ right_high[x][e] ] > H[y]) continue;
else if(H[ right_high[x][e] ] == H[y]) return 1;
if(dist(x, right_high[x][e]) + dist(right_high[x][e], y) > dist(x, y))
continue;
x = right_high[x][e];
}
if(dist(x, y) < K || dist(y, x) < K)
{
return H[x] < H[y];
}
return 0;
}
bool query_left(int x, int y)
{
if(dist(x, y) < K || dist(y, x) < K)
{
return H[x] < H[y];
}
for(int e = lgN - 1; e >= 0; e--)
{
if(H[ left_high[x][e] ] > H[y]) continue;
else if(H[ left_high[x][e] ] == H[y]) return 1;
if(dist(left_high[x][e], x) + dist(y, left_high[x][e]) > dist(y, x))
continue;
x = left_high[x][e];
}
if(dist(x, y) < K || dist(y, x) < K)
{
return H[x] < H[y];
}
return 0;
}
int compare_plants(int x, int y)
{
if(query_left(x, y)) return -1;
if(query_right(x, y)) return -1;
if(query_left(y, x)) return 1;
if(query_right(y, x)) return 1;
return 0;
}
