#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(int L = 0, int R = n - 1, int id = 0){
if(L == R){
st[id].mn = rec[L];
st[id].pos = L;
return;
}
int M = (L + R) / 2;
build(L, M, lc);
build(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);
}
}
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;
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();
for(int i = n - 1; i >= 0; i--){
solve(i);
}
rk.eb(rk[0]);
// right 0 > x
{
deque<int> dq;
dq.eb(0);
for(int i = 1; i < n; i++){
while(!dq.empty() && dq.front() <= i - K) dq.pof;
if(dq.empty()) break;
if(rk[dq.front()] < rk[i]) continue;
ans[i] = 1;
while(!dq.empty() && rk[dq.back()] < rk[i]) dq.pob;
dq.eb(i);
}
}
// left 0 > x
{
deque<int> dq;
dq.eb(n);
for(int i = n - 1; i > 1; i--){
while(!dq.empty() && dq.front() >= i + K) dq.pof;
if(dq.empty()) break;
if(rk[dq.front()] < rk[i]) continue;
ans[i] = 1;
while(!dq.empty() && rk[dq.back()] < rk[i]) dq.pob;
dq.eb(i);
}
}
// right 0 < x
{
deque<int> dq;
dq.eb(0);
for(int i = 1; i < n; i++){
while(!dq.empty() && dq.front() <= i - K) dq.pof;
if(dq.empty()) break;
if(rk[dq.front()] > rk[i]) continue;
ans[i] = -1;
while(!dq.empty() && rk[dq.back()] > rk[i]) dq.pob;
dq.eb(i);
}
}
// left 0 < x
{
deque<int> dq;
dq.eb(n);
for(int i = n - 1; i > 1; i--){
while(!dq.empty() && dq.front() >= i + K) dq.pof;
if(dq.empty()) break;
if(rk[dq.front()] > rk[i]) continue;
ans[i] = -1;
while(!dq.empty() && rk[dq.back()] > rk[i]) dq.pob;
dq.eb(i);
}
}
}
int compare_plants(int x, int y){
if(x != 0) return 0;
return ans[y];
}
