#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
typedef long long ll;
#define pb push_back
const int INF = (int)1e9;
array<int, 2> nl = {INF, INF};
struct segtree{
vector<array<int, 2>> tree;
vector<int> lazy;
int n;
void push(int v){
lazy[v << 1] += lazy[v];
lazy[v << 1 | 1] += lazy[v];
tree[v << 1][0] += lazy[v];
tree[v << 1 | 1][0] += lazy[v];
lazy[v] = 0;
}
array<int, 2> comb(array<int, 2> a, array<int, 2> b){
if(a[0] == b[0]){
if(a[1] < b[1])
swap(a, b);
if(a[1] - b[1] > (b[1] + n - a[1]))
return b;
else
return a;
}
else{
return min(a, b);
}
}
segtree(){}
segtree(int sz, vector<array<int, 2>> &init){
n = 1;
while(n < sz) n *= 2;
tree.resize(2 * n, nl);
lazy.resize(2 * n, 0);
REP(i, n){
if(i < init.size())
tree[i + n] = init[i];
}
FORD(i, n - 1, 1, 1)
tree[i] = comb(tree[i << 1], tree[i << 1 | 1]);
}
void upd(int l, int r, int val){ upd0(l, r, 0, n, 1, val); }
void upd0(int l, int r, int beg, int end, int v, int val){
if(beg >= l && end <= r){
tree[v][0] += val;
lazy[v] += val;
return;
}
if(beg >= r || end <= l)
return;
push(v);
int mid = (beg + end) >> 1;
upd0(l, r, beg, mid, v << 1, val);
upd0(l, r, mid, end, v << 1 | 1, val);
tree[v] = comb(tree[v << 1], tree[v << 1 | 1]);
}
array<int, 2> query(int l, int r){return query0(l, r, 0, n, 1); }
array<int, 2> query0(int l, int r, int beg, int end, int v){
if(beg >= l && end <= r)
return tree[v];
if(beg >= r || end <= l)
return nl;
push(v);
int mid = (beg + end) >> 1;
return comb(query0(l, r, beg, mid, v << 1),query0(l, r, mid, end, v << 1 | 1));
}
};
segtree st;
int n;
vector<int> pos;
void init(int k, std::vector<int> r) {
n = r.size();
pos.resize(n, 0);
vector<array<int, 2>> in(n);
REP(i, n){
in[i] = {r[i], i};
}
st = segtree(n, in);
int curr = 0;
REP(i, n){
auto x = st.query(0, n);
pos[x[1]] = curr++;
st.upd(x[1], x[1] + 1, INF);
int r = x[1];
int l = x[1] - (k - 1);
if(l >= 0){
st.upd(l, r, -1);
}
else{
st.upd(0, r, -1);
l += n,
st.upd(l, n, -1);
}
}
}
int compare_plants(int x, int y) {
if(pos[x] < pos[y])
return 1;
else
return -1;
}
