// In the name of Allah
#include <bits/stdc++.h>
#include "plants.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct node {
ll lazy; pll min;
};
const int maxn = 2e5 + 7;
const ll oo = 1e9 + 7;
int n, k;
int A[maxn], val[maxn];
set<int> st, stx;
node t[4 * maxn];
void build(int v, int tl, int tr) {
t[v].lazy = 0;
if (tr - tl == 1) {
t[v].min = Mp(A[tl], tl);
return ;
}
int mid = (tl + tr) / 2;
build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
t[v].min = min(t[2 * v + 1].min, t[2 * v + 2].min); t[v].min.F += t[v].lazy;
}
void add_val(int v, int tl, int tr, int l, int r, ll x) {
l = max(l, tl); r = min(r, tr);
if (l >= tr || r <= tl) return ;
if (l == tl && r == tr) {
t[v].min.F += x; t[v].lazy += x;
return ;
}
int mid = (tl + tr) / 2;
add_val(2 * v + 1, tl, mid, l, r, x); add_val(2 * v + 2, mid, tr, l, r, x);
t[v].min = min(t[2 * v + 1].min, t[2 * v + 2].min); t[v].min.F += t[v].lazy;
}
void checkx(int j) {
stx.erase(j); int d = 0;
auto it = st.lower_bound(j);
if (it != st.begin()) {
it--; d = (j - *it);
}
else d = (j - *st.rbegin() + n);
if (d >= k) stx.insert(j);
}
void addx(int j) {
st.insert(j); checkx(j);
if (len(st) == 1) return ;
auto it = st.upper_bound(j);
if (it != st.end()) checkx(*it);
else checkx(*st.begin());
}
void delx(int j) {
st.erase(j); stx.erase(j);
if (len(st) == 0) return ;
auto it = st.upper_bound(j);
if (it != st.end()) checkx(*it);
else checkx(*st.begin());
}
void init(int Kx, vector<int> Ax) {
n = len(Ax); k = Kx;
for (int i = 0; i < n; i++) A[i] = Ax[i];
build(0, 0, n);
int sz = 0;
while (sz < n) {
while (t[0].min.F == 0) {
int j = t[0].min.S;
add_val(0, 0, n, j, j + 1, oo);
addx(j);
}
int j = *stx.begin(); val[j] = sz++;
int x1 = min(j, k - 1), x2 = (k - 1) - x1;
add_val(0, 0, n, j - x1, j, -1);
add_val(0, 0, n, n - x2, n, -1);
delx(j);
}
return;
}
int compare_plants(int x, int y) {
if (val[x] < val[y]) return 1;
else return -1;
}
