#include <bits/stdc++.h>
#include "plants.h"
using namespace std;
#define MAXN 200005
#define debug(...) fprintf(stderr, __VA_ARGS__); fflush(stderr);
const int TS = 1<<20, ST = TS/2-1;
int N, K, R[MAXN*2];
int A[MAXN*2], B[MAXN*2];
struct SegTree{
template <typename T>
struct Value{
T value, lazysum;
};
Value<int> tree[TS];
void build(int arr[]){
memset(tree, 0, sizeof(tree));
for (int i=ST+1;i<TS;i++) tree[i].value = i-ST <= N+N ? arr[i-ST] : 1e9;
for (int i=ST;i;i--) tree[i].value = min(tree[i*2].value, tree[i*2+1].value);
}
void propagate(int n){
if (n <= ST){
tree[n*2].value += tree[n].lazysum, tree[n*2+1].value += tree[n].lazysum;
tree[n*2].lazysum += tree[n].lazysum, tree[n*2+1].lazysum += tree[n].lazysum;
}
tree[n].lazysum = 0;
}
void update(int n, int s, int e, int l, int r, const int &v){
if (l > r || e < l || r < s) return;
if (l <= s && e <= r){
tree[n].value += v, tree[n].lazysum += v;
return;
}
propagate(n);
int m = s+e >> 1;
update(n*2, s, m, l, r, v);
update(n*2+1, m+1, e, l, r, v);
tree[n].value = min(tree[n*2].value, tree[n*2+1].value);
}
int findzero(int n){
if (tree[n].value != 0) return 0;
propagate(n);
if (n > ST) return n-ST;
if (!tree[n*2].value) return findzero(n*2);
else if (!tree[n*2+1].value) return findzero(n*2+1);
else assert(0);
}
} segtree;
void get(int perm[])
{
segtree.build(R);
stack <int> wait;
for (int ord=1;ord<=N+N;ord++){
int x = segtree.findzero(1);
while (!x){
int q = wait.top(); wait.pop();
segtree.update(1, 1, TS/2, q, N+N, -1);
x = segtree.findzero(1);
}
perm[x] = ord;
segtree.update(1, 1, TS/2, x, x, 1e9);
segtree.update(1, 1, TS/2, max(1, x-K+1), x-1, -1);
if (x-K+1 < 1) wait.push(N+N-(1-(x-K+1))+1);
}
}
void init(int K, vector<int> r)
{
::K = K;
N = r.size();
for (int i=1;i<=N;i++) R[N+i] = R[i] = r[i-1];
get(A);
for (int i=1;i<=N+N;i++) R[i] = K-R[i]-1;
get(B);
}
int compare_plants(int x, int y)
{
if (x > y) return -compare_plants(y, x);
x++; y++;
if (A[x] > A[y] || B[y] > B[x+N]) return -1;
if (B[x] > B[y] || A[y] > A[x+N]) return 1;
return 0;
}
