#include "plants.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <map>
typedef long long llong;
const int MAXN = 200000 + 10;
const int MAXLOG = 18;
const int INF = 2e9;
int n, k;
struct SegmentTree
{
struct Node
{
int min;
int idx;
int lazy;
Node()
{
min = INF;
idx = -1;
lazy = 0;
}
friend Node operator + (const Node &left, const Node &right)
{
if (left.min < right.min)
{
return left;
} else
{
return right;
}
}
};
Node tree[4*MAXN];
void build(int l, int r, int node, int vals[])
{
if (l == r)
{
tree[node].min = vals[l];
tree[node].idx = l;
return;
}
int mid = l + r >> 1;
build(l, mid, 2*node, vals);
build(mid + 1, r, 2*node + 1, vals);
tree[node] = tree[2*node] + tree[2*node + 1];
}
void push(int node, int l, int r)
{
if (tree[node].lazy == 0)
{
return;
}
tree[node].min += tree[node].lazy;
if (l < r)
{
tree[2*node].lazy += tree[node].lazy;
tree[2*node + 1].lazy += tree[node].lazy;
}
tree[node].lazy = 0;
}
void update(int l, int r, int node, int queryL, int queryR, int queryVal)
{
push(node, l, r);
if (queryR < l || r < queryL)
{
return;
}
if (queryL <= l && r <= queryR)
{
tree[node].lazy = queryVal;
push(node, l, r);
return;
}
int mid = l + r >> 1;
update(l, mid, 2*node, queryL, queryR, queryVal);
update(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
tree[node] = tree[2*node] + tree[2*node + 1];
}
Node query(int l, int r, int node, int queryL, int queryR)
{
push(node, l, r);
if (queryL <= l && r <= queryR)
{
return tree[node];
}
Node result;
int mid = l + r >> 1;
if (queryL <= mid) result = result + query(l, mid, 2*node, queryL, queryR);
if (mid + 1 <= queryR) result = result + query(mid + 1, r, 2*node + 1, queryL, queryR);
return result;
}
void build(int r[])
{
build(1, n, 1, r);
}
void update(int l, int r, int val)
{
update(1, n, 1, l, r, val);
}
Node query(int l, int r)
{
return query(1, n, 1, l, r);
}
};
struct Fenwick
{
int tree[MAXN];
void reset()
{
std::fill(tree + 1, tree + 1 + n, 0);
}
void update(int idx, int val)
{
for (; idx <= n ; idx += idx & (-idx))
{
tree[idx] += val;
}
}
int query(int idx)
{
int res = 0;
for (; idx ; idx -= idx & (-idx))
{
res += tree[idx];
}
return res;
}
int kth(int k)
{
int idx = 0;
for (int lg = MAXLOG - 1 ; lg >= 0 ; --lg)
{
if (idx + (1 << lg) <= n && tree[idx + (1 << lg)] < k)
{
idx += (1 << lg);
k -= tree[idx];
}
}
return idx + 1;
}
};
int h[2 * MAXN];
struct Sparse
{
int sparse[MAXLOG + 1][2 * MAXN];
void build(int jump[])
{
for (int i = 1 ; i <= 2 * n ; ++i)
{
sparse[0][i] = jump[i];
}
for (int lg = 1 ; (1 << lg) <= 2 * n ; ++lg)
{
for (int u = 1 ; u <= 2 * n ; ++u)
{
sparse[lg][u] = sparse[lg - 1][sparse[lg - 1][u]];
}
}
}
bool jumpLeft(int from, int to)
{
for (int lg = MAXLOG ; lg >= 0 ; --lg)
{
if (sparse[lg][from] != 0 && sparse[lg][from] >= to)
{
from = sparse[lg][from];
}
}
if (from - k + 1 <= to && h[from] >= h[to]) return true;
return false;
}
bool jumpRight(int from, int to)
{
for (int lg = MAXLOG ; lg >= 0 ; --lg)
{
if (sparse[lg][from] != 0 && sparse[lg][from] <= to)
{
from = sparse[lg][from];
}
}
if (from + k - 1 >= to && h[from] >= h[to]) return true;
return false;
}
};
Fenwick fenwick;
SegmentTree tree;
Sparse sparsePrev;
Sparse sparseNext;
int r[MAXN];
int prev[2 * MAXN];
int next[2 * MAXN];
int ptrH;
void rec(int idx)
{
while (true)
{
SegmentTree::Node res;
if (idx > 1) res = res + tree.query(std::max(1, idx - k + 1), idx - 1);
if (idx < k) res = res + tree.query(n - (k - idx) + 1, n);
if (res.min == 0)
{
rec(res.idx);
} else
{
break;
}
}
h[idx] = ptrH--;
tree.update(idx, idx, 2 * n);
if (idx > 1) tree.update(std::max(1, idx - k + 1), idx, -1);
if (idx < k) tree.update(n - (k - idx) + 1, n, -1);
}
std::map <int,int> toIndex;
void init(int K, std::vector <int> R)
{
k = K;
n = R.size();
for (int i = 1 ; i <= n ; ++i)
{
r[i] = R[i - 1];
}
ptrH = n;
tree.build(r);
while (ptrH > 0)
{
SegmentTree::Node res = tree.query(1, n);
assert(res.min == 0);
rec(res.idx);
}
for (int i = n + 1 ; i <= 2 * n ; ++i)
{
h[i] = h[i - n];
}
for (int i = 1 ; i < k ; ++i)
{
toIndex[h[i]] = i;
fenwick.update(h[i], 1);
}
for (int i = k ; i <= 2 * n ; ++i)
{
if (fenwick.query(h[i]) == 0)
{
prev[i] = 0;
} else
{
prev[i] = toIndex[fenwick.kth(fenwick.query(h[i]))];
}
toIndex[h[i - k + 1]] = 0;
toIndex[h[i]] = i;
fenwick.update(h[i - k + 1], -1);
fenwick.update(h[i], 1);
}
toIndex.clear();
fenwick.reset();
for (int i = 2 * n ; i > 2 * n - k + 1 ; --i)
{
toIndex[h[i]] = i;
fenwick.update(h[i], 1);
}
for (int i = 2 * n - k + 1 ; i >= 1 ; --i)
{
if (fenwick.query(h[i]) == 0)
{
next[i] = 0;
} else
{
next[i] = toIndex[fenwick.kth(fenwick.query(h[i]))];
}
toIndex[h[i + k - 1]] = 0;
toIndex[h[i]] = i;
fenwick.update(h[i + k - 1], -1);
fenwick.update(h[i], 1);
}
sparsePrev.build(prev);
sparseNext.build(next);
}
int compare_plants(int x, int y)
{
x++; y++;
if (sparsePrev.jumpLeft(x + n, y) || sparseNext.jumpRight(x, y)) return 1;
if (sparsePrev.jumpLeft(y, x) || sparseNext.jumpRight(y, n + x)) return -1;
return 0;
}
