#include <bits/stdc++.h>
#include "plants.h"
using namespace std;
#define ll long long
const int mxn = 2e5 + 100;
int n, k;
vector<int> R, vals;
struct SGT {
vector<pair<ll, ll>> sgt;
vector<ll> lz;
SGT(int sz) {
sgt.resize(4 * sz);
lz.resize(4 * sz);
}
void merge(int k) {
int ind = sgt[k * 2].second;
if (sgt[k * 2 + 1].first < sgt[k * 2].first) ind = sgt[k * 2 + 1].second;
sgt[k] = {min(sgt[k * 2].first, sgt[k * 2 + 1].first), ind};
}
void build(int k, int l, int r) {
if (l == r) {
sgt[k] = {R[l], l};
return;
}
int mid = (l + r) / 2;
build(k * 2, l, mid);
build(k * 2 + 1, mid + 1, r);
merge(k);
}
void push(int k, int l, int r) {
if (lz[k]) {
sgt[k].first += lz[k];
if (l != r) {
lz[k * 2] += lz[k];
lz[k * 2 + 1] += lz[k];
}
lz[k] = 0;
}
}
pair<ll, ll> get(int k, int l, int r, int i, int j) {
push(k, l, r);
if (l > j || r < i) return {1e8, 1e8};
if (i <= l && r <= j) return sgt[k];
int mid = (l + r) / 2;
pair<ll, ll> ansL, ansR;
ansL = get(k * 2, l, mid, i, j);
ansR = get(k * 2 + 1, mid + 1, r, i, j);
int ind = ansL.second;
if (ansR.first < ansL.first) ind = ansR.second;
return {min(ansL.first, ansR.first), ind};
}
void updateIND(int k, int l, int r, int i, ll val) {
push(k, l, r);
if (l > i || r < i) return;
if (l == r) {
sgt[k].first = val;
return;
}
int mid = (l + r) / 2;
updateIND(k * 2, l, mid, i, val);
updateIND(k * 2 + 1, mid + 1, r, i, val);
merge(k);
}
void update(int k, int l, int r, int i, int j) {
push(k, l, r);
if (l > j || r < i) return;
if (i <= l && r <= j) {
lz[k]--;
push(k, l, r);
return;
}
int mid = (l + r) / 2;
update(k * 2, l, mid, i, j);
update(k * 2 + 1, mid + 1, r, i, j);
merge(k);
}
} sgt(mxn);
int check(int pos) {
if (pos >= k) return sgt.get(1, 0, n - 1, pos - k, pos).second;
int left = k - pos - 1;
pair<ll, ll> f, s;
f = sgt.get(1, 0, n - 1, 0, pos);
s = sgt.get(1, 0, n - 1, n - 1 - left, n - 1);
if (s.first <= f.first) return s.second;
return f.second;
}
void update(int pos) {
if (pos >= k) sgt.update(1, 0, n - 1, pos - k, pos);
int left = k - pos - 1;
sgt.update(1, 0, n - 1, 0, pos);
sgt.update(1, 0, n - 1, n - 1 - left, n - 1);
}
void init(int _k, vector<int> _r) {
R = _r;
n = R.size();
k = _k;
k--;
vals.resize(n);
sgt.build(1, 0, n - 1);
for (int i = 0; i < n; i++) {
pair<ll, ll> get = sgt.get(1, 0, n - 1, 0, n - 1);
int pos = get.second;
set<int> s;
while (check(pos) != pos) {
pos = check(pos);
if (s.count(pos)) assert(0);
s.insert(pos);
}
update(pos);
vals[pos] = n - i;
sgt.updateIND(1, 0, n - 1, pos, 1e8);
}
}
int compare_plants(int x, int y) {
if (vals[x] == vals[y]) return 0;
return (vals[x] > vals[y] ? 1 : -1);
}
