#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 2e5 + 10;
const int inf = 1e6;
int n, k, a[maxn], val[maxn], seg[maxn << 2][2], lazy[maxn << 2][2];
void shift(int v, int x, int l, int r);
void add(int v, int x, int l, int r, int ql, int qr, int val){
//if (v == 1) debug(ql, qr, val);
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr){
// debug(l, r, ql, qr, val);
seg[v][x] += val;
lazy[v][x] += val;
return;
}
shift(v, x, l, r);
int mid = (l + r) >> 1;
add(v << 1, x, l, mid, ql, qr, val);
add(v << 1 | 1, x, mid, r, ql, qr, val);
seg[v][x] = min(seg[v<<1][x], seg[v<<1|1][x]);
}
int find0(int v, int x, int l, int r){
if (seg[v][x] != 0) return -1;
if (l + 1 == r) return l;
shift(v, x, l, r);
int mid = (l + r) >> 1;
int res = find0(v << 1, x, l, mid);
if (res == -1) return find0(v << 1 | 1, x, mid, r);
return res;
}
void shift(int v, int x, int l, int r){
if (lazy[v][x] == 0) return;
int mid = (l + r) >> 1;
add(v << 1, x, l, mid, l, mid, lazy[v][x]);
add(v << 1 | 1, x, mid, r, mid, r, lazy[v][x]);
lazy[v][x] = 0;
}
void init(int _k, std::vector<int> r) {
n = r.size();
k = _k;
for (int i = 0; i < n; i++){
a[i] = r[i];
add(1, 0, 0, n, i, i+1, a[i]);
add(1, 1, 0, n, i, i+1, a[i]);
}
vector<int> topol;
for (int i = 0; i < n; i++){
int tmp;
while((tmp = find0(1, 1, 0, n)) != -1){
//debug(tmp);
add(1, 0, 0, n, tmp+1, tmp+k, 1);
if (tmp+k > n){
add(1, 0, 0, n, 0, tmp+k-n, 1);
}
add(1, 1, 0, n, tmp, tmp+1, inf);
}
tmp = find0(1, 0, 0, n);
// debug(tmp);
add(1, 0, 0, n, tmp+1, tmp+k, -1);
if (tmp+k > n){
add(1, 0, 0, n, 0, tmp+k-n, -1);
}
add(1, 0, 0, n, tmp-k+1, tmp, -1);
add(1, 1, 0, n, tmp-k+1, tmp, -1);
if (tmp-k+1 < 0){
add(1, 0, 0, n, tmp-k+1+n, n, -1);
add(1, 1, 0, n, tmp-k+1+n, n, -1);
}
assert(tmp != -1);
topol.push_back(tmp);
val[tmp] = n-i;
add(1, 0, 0, n, tmp, tmp+1, inf);
}
k = _k;
}
int compare_plants(int x, int y) {
return (val[x] > val[y]? 1: -1);
return 0;
}
