#include "plants.h"
#include <bits/stdc++.h>
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define ef emplace_front
#define pob pop_back()
#define pof pop_front()
#define mp make_pair
#define F first
#define S second
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) { \
for(auto pv : a) b << pv << " "; \
b << "\n"; \
}
using namespace std;
typedef long long ll;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const ll MAX = 1e6;
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.F << ',' << p.S << ')';
}
void waassert(bool t){
if(t) return;
exit(0);
}
int n, K;
vector<int> rec;
vector<bool> use;
struct Node{
int mn = 0, pos = 0, tag = 0;
};
Node operator+(Node a, Node b){
Node c;
c.mn = min(a.mn, b.mn);
if(a.mn == c.mn) c.pos = a.pos;
else c.pos = b.pos;
return c;
}
vector<Node> st;
#define lc 2 * id + 1
#define rc 2 * id + 2
void build(vector<int>& o, int L = 0, int R = n - 1, int id = 0){
if(L == R){
st[id].mn = o[L];
st[id].pos = L;
return;
}
int M = (L + R) / 2;
build(o, L, M, lc);
build(o, M + 1, R, rc);
st[id] = st[lc] + st[rc];
}
void addtag(int v, int id){
st[id].tag += v;
st[id].mn += v;
}
void push(int id){
addtag(st[id].tag, lc);
addtag(st[id].tag, rc);
st[id].tag = 0;
}
void _modify(int l, int r, int v, int L = 0, int R = n - 1, int id = 0){
if(l <= L && R <= r){
addtag(v, id);
return;
}
push(id);
int M = (L + R) / 2;
if(r <= M) _modify(l, r, v, L, M, lc);
else if(l > M) _modify(l, r, v, M + 1, R, rc);
else{
_modify(l, r, v, L, M, lc);
_modify(l, r, v, M + 1, R, rc);
}
st[id] = st[lc] + st[rc];
}
void modify(int l, int r, int v){
l = (l % n + n) % n;
r = (r % n + n) % n;
if(l <= r) _modify(l, r, v);
else{
_modify(l, n - 1, v);
_modify(0, r, v);
}
}
Node _query(int l, int r, int L = 0, int R = n - 1, int id = 0){
if(l <= L && R <= r) return st[id];
push(id);
int M = (L + R) / 2;
if(r <= M) return _query(l, r, L, M, lc);
else if(l > M) return _query(l, r, M + 1, R, rc);
else return _query(l, r, L, M, lc) + _query(l, r, M + 1, R, rc);
}
Node query(int l, int r){
l = (l % n + n) % n;
r = (r % n + n) % n;
if(l <= r) return _query(l, r);
else{
return _query(l, n - 1) + _query(0, r);
}
}
void _print(int L = 0, int R = n - 1, int id = 0){
if(L == R){
cerr << st[id].mn << " ";
return;
}
push(id);
int M = (L + R) / 2;
_print(L, M, lc);
_print(M + 1, R, rc);
}
void print(){
_print();
cerr << "\n";
}
int getdis(int l, int r){
l = (l % n + n) % n;
r = (r % n + n) % n;
if(l == r) return n;
if(l > r) r += n;
return r - l;
}
set<int> zero;
set<pii> sep;
vector<int> rk;
void solve(int _rk){
while(st[0].mn == 0){
int pos = st[0].pos;
modify(pos, pos, MAX);
if(zero.empty()){
zero.insert(pos);
sep.insert(mp(n, pos));
continue;
}
auto it = zero.lower_bound(pos);
if(it == zero.end()) it = zero.begin();
int nxt = *it;
int lst = it == zero.begin() ? *zero.rbegin() : *prev(it);
sep.erase(mp(getdis(lst, nxt), nxt));
sep.insert(mp(getdis(lst, pos), pos));
sep.insert(mp(getdis(pos, nxt), nxt));
zero.insert(pos);
}
int pos = sep.rbegin()->S;
if(zero.size() == 1){
sep.clear();
zero.clear();
}
else{
auto it = zero.lower_bound(pos);
int nxt = next(it) == zero.end() ? *zero.begin() : *next(it);
int lst = it == zero.begin() ? *zero.rbegin() : *prev(it);
sep.erase(mp(getdis(lst, pos), pos));
sep.erase(mp(getdis(pos, nxt), nxt));
sep.insert(mp(getdis(lst, nxt), nxt));
zero.erase(pos);
}
use[pos] = true;
rk[pos] = _rk;
modify(pos - K + 1, pos - 1, -1);
}
vector<int> ans;
vector<vector<int>> ri, le;
void init(int k, vector<int> _r){
K = k;
rec = _r;
n = rec.size();
st.resize(4 * n);
use.resize(n);
rk.resize(n);
ans.resize(n);
build(rec);
for(int i = n - 1; i >= 0; i--){
solve(i);
}
le.resize(20, vector<int>(n));
ri.resize(20, vector<int>(n));
{
vector<int> tmp(n, 1);
build(tmp);
}
vector<int> pos(n);
for(int i = 0; i < n; i++) pos[rk[i]] = i;
for(int i = 0; i < n; i++){
Node tmp = query(pos[i] + 1, pos[i] + k - 1);
if(tmp.mn != 1){
int nxt = tmp.pos;
ri[0][pos[i]] = getdis(pos[i], nxt);
/*cerr << "right " << pos[i] << " : " << nxt << "\n";
cerr << pos[i] + 1 << " " << pos[i] + k - 1 << "\n";*/
}
tmp = query(pos[i] - k + 1, pos[i] - 1);
if(tmp.mn != 1){
int nxt = tmp.pos;
le[0][pos[i]] = getdis(nxt, pos[i]);
/*cerr << "left " << pos[i] << " : " << nxt << "\n";
cerr << pos[i] - k + 1 << " " << pos[i] - 1 << "\n";*/
}
modify(pos[i], pos[i], -i);
}
for(int i = 1; i < 20; i++){
for(int j = 0; j < n; j++){
int nxt = j - le[i - 1][j];
nxt = (nxt % n + n) % n;
le[i][j] = le[i - 1][j] + le[i - 1][nxt];
nxt = j + ri[i - 1][j];
nxt = nxt % n;
ri[i][j] = ri[i - 1][j] + ri[i - 1][nxt];
}
}
/*cerr << "rank ";
printv(rk, cerr);
cerr << "left ";
printv(le[0], cerr);
cerr << "right ";
printv(ri[0], cerr);*/
}
bool checkgreater(int x, int y){
// right
{
int dis = getdis(x, y);
int tmp = 0;
int now = x;
for(int i = 19; i >= 0; i--){
if(tmp + ri[i][now] >= dis - K + 1) continue;
tmp += ri[i][now];
now = (x + tmp) % n;
}
if(tmp < dis - K + 1){
tmp += ri[0][now];
now = (x + tmp) % n;
}
if(tmp >= dis - K + 1 && rk[now] > rk[y]) return true;
}
// left
{
int dis = getdis(y, x);
int tmp = 0;
int now = x;
for(int i = 19; i >= 0; i--){
if(tmp + le[i][now] >= dis - K + 1) continue;
tmp += le[i][now];
now = ((x - tmp) % n + n) % n;
}
if(tmp < dis - K + 1){
tmp += le[0][now];
now = ((x - tmp) % n + n) % n;
}
if(tmp >= dis - K + 1 && rk[now] > rk[y]) return true;
}
return false;
}
int compare_plants(int x, int y){
if(checkgreater(x, y)) return 1;
if(checkgreater(y, x)) return -1;
return 0;
}
