#include "plants.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 200'000;
int n, k;
int rk[MAXN + 10];
int dist(int s, int t) {
if(s <= t) return t - s;
else return t - s + n;
}
#define L(id) ((id) * 2 + 1)
#define R(id) ((id) * 2 + 2)
struct SegTree {
int add[MAXN * 4 + 10];
pii mn[MAXN * 4 + 10]; // {index, value}
pii comp(pii a, pii b) {
if(a.S < b.S) return a;
if(b.S < a.S) return b;
if(dist(a.F, b.F) < k) return a;
return b;
}
void pull(int id) {
mn[id] = comp(mn[L(id)], mn[R(id)]);
mn[id].S += add[id];
}
void build(int id, int l, int r, vector<int> &owo) {
add[id] = 0;
if(l == r) {
mn[id] = pii(l, owo[l]);
return;
}
int m = (l + r) / 2;
build(L(id), l, m, owo);
build(R(id), m + 1, r, owo);
pull(id);
}
void range_add(int id, int l, int r, int L, int R, int val) {
if(L > R) {
range_add(id, l, r, L, n - 1, val);
range_add(id, l, r, 0, R, val);
return;
}
if(l >= L && r <= R) {
add[id] += val;
mn[id].S += val;
return;
}
int m = (l + r) / 2;
if(L <= m) range_add(L(id), l, m, L, R, val);
if(R > m) range_add(R(id), m + 1, r, L, R, val);
pull(id);
}
} seg;
void init(int __k, vector<int> r) {
k = __k;
n = sz(r);
vector<int> alive(n, 1);
seg.build(0, 0, n - 1, r);
For(rank, 1, n) {
int idx = seg.mn[0].F;
// cerr << idx << "\n";
// For(i, 0, n - 1) cerr << r[i] << " \n"[i == n - 1];
seg.range_add(0, 0, n - 1, (idx + n - k + 1) % n, (idx + n - 1) % n, -1);
seg.range_add(0, 0, n - 1, idx, idx, n * 888);
alive[idx] = 0;
rk[idx] = rank;
}
}
int compare_plants(int x, int y) {
if(rk[x] < rk[y]) return 1;
return -1;
}
