#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
const int MAXN = 8e5+5;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second
int n, k, lz1[MAXN], lz2[MAXN];
pii seg1[MAXN], seg2[MAXN];
vi v, ord;
void build(int node, int l, int r) {
if(l == r) {
seg1[node] = mk(v[l],l);
seg2[node] = mk(1,l);
return;
}
int mid = (l+r)/2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
seg1[node] = min(seg1[2*node], seg1[2*node+1]);
seg2[node] = min(seg2[2*node], seg2[2*node+1]);
}
void prop1(int node, int flag) {
seg1[node].fr += lz1[node];
if(flag) {
lz1[2*node] += lz1[node];
lz1[2*node+1] += lz1[node];
}
lz1[node] = 0;
}
void update1(int node, int l, int r, int p, int q, int val) {
if(q >= n) update1(node, l, r, 0, q-n, val), q = n-1;
prop1(node, l != r);
if(r < p or q < l) return;
if(p <= l and r <= q) {
lz1[node] = val;
prop1(node, l != r);
return;
}
int mid = (l+r)/2;
update1(2*node, l, mid, p, q, val);
update1(2*node+1, mid+1, r, p, q, val);
seg1[node] = min(seg1[2*node], seg1[2*node+1]);
}
void prop2(int node, int flag) {
seg2[node].fr += lz2[node];
if(flag) {
lz2[2*node] += lz2[node];
lz2[2*node+1] += lz2[node];
}
lz2[node] = 0;
}
void update2(int node, int l, int r, int p, int q, int val) {
if(q >= n) update2(node, l, r, 0, q-n, val), q = n-1;
prop2(node, l != r);
if(r < p or q < l) return;
if(p <= l and r <= q) {
lz2[node] = val;
prop2(node, l != r);
return;
}
int mid = (l+r)/2;
update2(2*node, l, mid, p, q, val);
update2(2*node+1, mid+1, r, p, q, val);
seg2[node] = min(seg2[2*node], seg2[2*node+1]);
}
void init(int K, vector<int> r) {
n = sz(r);
v = r;
k = K;
ord.resize(n);
build(1,0,n-1);
for(int t = 0; t < n; t++) {
while(seg1[1].fr == 0) {
update2(1, 0, n-1, seg1[1].sc+1, seg1[1].sc+k-1, 1); // ATENCAO
update2(1, 0, n-1, seg1[1].sc, seg1[1].sc, -1);
update1(1, 0, n-1, seg1[1].sc, seg1[1].sc, 1e9);
}
int at = seg2[1].sc;
ord[at] = t;
update2(1, 0, n-1, at, at, 1e9);
update1(1, 0, n-1, (at-k+1+n)%n, (at-1+n)%n, -1);
}
}
int compare_plants(int x, int y) {
if(ord[x] < ord[y]) return 1;
return -1;
}
