#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9;
int n, a[200200], b[200200], idxa[200200], idxb[200200];
struct Seg2{
pair<int, int> tree[800800];
int lazy[800800];
void init(int i, int l, int r){
lazy[i] = 0;
if (l==r) {tree[i] = {INF, l}; return;}
int m = (l+r)>>1;
init(i<<1, l, m); init(i<<1|1, m+1, r);
tree[i] = min(tree[i<<1], tree[i<<1|1]);
}
void propagate(int i, int l, int r){
tree[i].first += lazy[i];
if (l!=r) lazy[i<<1] += lazy[i], lazy[i<<1|1] += lazy[i];
lazy[i] = 0;
}
void update(int i, int l, int r, int s, int e, int x){
propagate(i, l, r);
if (r<s || e<l) return;
if (s<=l && r<=e){
lazy[i] += x;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i<<1, l, m, s, e, x); update(i<<1|1, m+1, r, s, e, x);
tree[i] = min(tree[i<<1], tree[i<<1|1]);
}
void update2(int i, int l, int r, int s, int x){
propagate(i, l, r);
if (r<s || s<l) return;
if (l==r) {tree[i].second = x; return;}
int m = (l+r)>>1;
update2(i<<1, l, m, s, x); update2(i<<1|1, m+1, r, s, x);
tree[i] = min(tree[i<<1], tree[i<<1|1]);
}
void update(int l, int r, int x){
if (r<=n) update(1, 1, n, l, r, x);
else{
update(1, 1, n, l, n, x);
update(1, 1, n, 1, r-n, x);
}
}
}tree2;
struct Seg1{
int tree[800800], lazy[800800];
void init(int i, int l, int r, vector<int> &vec){
lazy[i] = 0;
if (l==r) {tree[i] = vec[l-1]; return;}
int m = (l+r)>>1;
init(i<<1, l, m, vec); init(i<<1|1, m+1, r, vec);
tree[i] = max(tree[i<<1], tree[i<<1|1]);
}
void propagate(int i, int l, int r){
tree[i] += lazy[i];
if (l!=r) lazy[i<<1] += lazy[i], lazy[i<<1|1] += lazy[i];
lazy[i] = 0;
}
void update(int i, int l, int r, int s, int e, int x){
propagate(i, l, r);
if (r<s || e<l) return;
if (s<=l && r<=e){
lazy[i] += x;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i<<1, l, m, s, e, x); update(i<<1|1, m+1, r, s, e, x);
tree[i] = max(tree[i<<1], tree[i<<1|1]);
}
void find(int i, int l, int r, int x){
propagate(i, l, r);
if (tree[i]<x) return;
if (l==r){
assert(tree[i]==x);
//printf("YES: %d\n", l);
tree2.update(l, l, -INF);
tree2.update(l+1, l+x, 1);
update(1, 1, n, l, l, -INF);
return;
}
int m = (l+r)>>1;
find(i<<1, l, m, x); find(i<<1|1, m+1, r, x);
tree[i] = max(tree[i<<1], tree[i<<1|1]);
}
void update(int s, int e, int x){
if (s>0) update(1, 1, n, s, e, x);
else{
update(1, 1, n, s+n, n, x);
update(1, 1, n, 1, e, x);
}
}
}tree1;
struct Seg3{
pair<int, int> tree[400400];
int sz;
void init(int n, int *a){
sz = n+1;
for (int i=sz;i<sz*2;i++) tree[i] = {a[i-sz], i-sz};
for (int i=sz-1;i;i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);
}
void update(int p, int x){
for (tree[p+=sz].first=x;p>1;p>>=1) tree[p>>1] = min(tree[p], tree[p^1]);
}
pair<int, int> query(int l, int r){
pair<int, int> ret = {INF, -1};
for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
if (l&1) ret = min(ret, tree[l++]);
if (r&1) ret = min(ret, tree[--r]);
}
return ret;
}
int queryc(int l, int r){
if (l<=0){
auto p = min(query(l+n, sz), query(1, r+1));
return p.second;
}
if (r>n){
auto p = min(query(l, sz), query(1, r-n+1));
return p.second;
}
return query(l, r+1).second;
}
}tree3;
vector<int> r, adj[200200];
int k, ans1[200200], ans2[200200], cnt1, cnt2, in[200200];
bool visited1[200200], visited2[200200];
void dfs1(int s){
visited1[s] = 1;
for (auto &v:adj[s]) if (!visited1[v]) dfs1(v);
ans1[s] = cnt1--;
}
void dfs2(int s){
visited2[s] = 1;
if (adj[s].size()==2 && ans1[adj[s][0]] > ans1[adj[s][1]]) swap(adj[s][0], adj[s][1]);
for (auto &v:adj[s]) if (!visited2[v]) dfs2(v);
ans2[s] = cnt2--;
}
void init(int K, vector<int> R) {
k = K, r = R;
n = r.size();
tree1.init(1, 1, n, r);
tree2.init(1, 1, n);
tree2.update2(1, 1, n, 1, INF+1);
for (int i=1;i<=n;i++){
tree1.find(1, 1, n, k-1);
assert(tree2.tree[1].first==0);
a[i] = tree2.tree[1].second;
if (a[i]>=INF) a[i] -= INF;
//printf("a[%d] = %d\n", i, a[i]);
tree2.update(a[i], a[i], INF);
tree2.update(a[i]+1, a[i]+k-1, -1);
tree1.update(a[i]-k+1, a[i]-1, 1);
}
for (int i=1;i<=n;i++) idxa[a[i]] = i;
//printf("idxa: ");
//for (int i=1;i<=n;i++) printf("%d ", idxa[i]);
//printf("\n");
tree3.init(n, idxa);
for (int i=1;i<=n;i++){
int pos = a[i];
int l = tree3.queryc(pos-k+1, pos-1), r = tree3.queryc(pos+1, pos+k-1);
if (l!=-1){
adj[pos].push_back(l);
in[l]++;
}
if (r!=-1){
adj[pos].push_back(r);
in[r]++;
}
//printf("%d: %d %d\n", pos, l, r);
tree3.update(pos, INF+1);
}
for (int i=1;i<=n;i++) if (!in[i]) adj[0].push_back(i);
cnt1 = cnt2 = n;
dfs1(0);
dfs2(0);
//for (int i=1;i<=n;i++) printf("%d ", ans1[i]);
//printf("\n");
//for (int i=1;i<=n;i++) printf("%d ", ans2[i]);
//printf("\n");
}
int compare_plants(int x, int y) {
++x, ++y;
if (ans1[x] < ans1[y] && ans2[x] < ans2[y]) return -1;
if (ans1[y] < ans1[x] && ans2[y] < ans2[x]) return 1;
return 0;
}
