#include <bits/stdc++.h>
#include "plants.h"
using namespace std;
typedef long long ll;
struct segTree{
pair<int, int> tree[800002];
int lazy[800002];
void init(int i, int l, int r, int *A){
lazy[i] = 0;
if(l==r){
tree[i] = make_pair(A[l], l);
return;
}
int m = (l+r)>>1;
init(i*2, l, m, A);
init(i*2+1, m+1, r, A);
tree[i] = min(tree[i*2], tree[i*2+1]);
}
void propagate(int i, int l, int r){
tree[i].first += lazy[i];
if(l!=r){
lazy[i*2] += lazy[i];
lazy[i*2+1] += lazy[i];
}
lazy[i] = 0;
}
void add(int i, int l, int r, int s, int e, int val){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
lazy[i] += val;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
add(i*2, l, m, s, e, val);
add(i*2+1, m+1, r, s, e, val);
tree[i] = min(tree[i*2], tree[i*2+1]);
}
pair<int, int> findMin(int i, int l, int r, int s, int e){
propagate(i, l, r);
if(r<s || e<l) return make_pair(INT_MAX, INT_MAX);
if(s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return min(findMin(i*2, l, m, s, e), findMin(i*2+1, m+1, r, s, e));
}
} tree;
int n, k;
int arr[200002];
int sum[200002];
int ans[200002];
void init(int _k, vector<int> r) {
n = (int)r.size();
k = _k;
for(int i=1; i<=n; i++) arr[i] = r[i-1];
tree.init(1, 1, n, arr);
for(int turn=n; turn>=1; turn--){
int minLoc = tree.findMin(1, 1, n, 1, n).second;
if(minLoc < k){
auto tmp = tree.findMin(1, 1, n, n-(k-minLoc)+1, n);
if(tmp.first == 0) minLoc = tmp.second;
}
ans[minLoc] = turn;
tree.add(1, 1, n, minLoc, minLoc, 1000000000);
if(minLoc >= k) tree.add(1, 1, n, minLoc-k+1, minLoc, -1);
else{
tree.add(1, 1, n, 1, minLoc, -1);
tree.add(1, 1, n, n-(k-minLoc)+1, n, -1);
}
}
}
int compare_plants(int x, int y) {
x++, y++;
if(ans[x] > ans[y]) return 1;
return -1;
}
