#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
const ll INF=1e18;
struct node{
int s,e,m;
ii val;
ll lazy=0;
node *l,*r;
node (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
val=ii(0,s);
if (s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void propo(){
if (lazy){
val.fi+=lazy;
if (s!=e){
l->lazy+=lazy;
r->lazy+=lazy;
}
lazy=0;
}
}
void update(int i,int j,ll k){
propo();
if (s==i && e==j) lazy+=k;
else{
if (j<=m) l->update(i,j,k);
else if (m<i) r->update(i,j,k);
else l->update(i,m,k),r->update(m+1,j,k);
l->propo(),r->propo();
val=min(l->val,r->val);
}
}
int query(int i){
propo();
if (s==e) return val.fi;
else if (i<=m) return l->query(i);
else return r->query(i);
}
} *root,*root2;
int n;
void update(int i,int j,ll k){
//cout<<i<<" "<<j<<" "<<k<<endl;
if (i<=j) root->update(i,j,k);
else root->update(i,n-1,k),root->update(0,j,k);
}
void update2(int i,int j,ll k){
//cout<<i<<" "<<j<<endl;
if (i<=j) root2->update(i,j,k);
else root2->update(i,n-1,k),root2->update(0,j,k);
}
vector<int> construct_fast(vector<int> v,int k){
n=sz(v);
vector<int> ans(n,0);
root=new node(0,n-1);
root2=new node(0,n-1);
rep(x,0,n) root->update(x,x,v[x]),root2->update(x,x,v[x]);
while (root2->val.fi==0){
int pos=root2->val.se;
root2->update(pos,pos,INF);
update((pos+1)%n,(pos+n/2)%n,1);
}
rep(val,n,0){
int idx=root->val.se;
//cout<<"curr: "<<idx<<" "<<root->val.fi<<endl;
ans[idx]=val;
update((idx+1)%n,(idx+n/2)%n,-1);
update((idx-(k-1)+n)%n,(idx-1+n)%n,-1);
update2((idx-(k-1)+n)%n,(idx-1+n)%n,-1);
//rep(x,0,n) cout<<root2->query(x)<<" "; cout<<endl;
while (root2->val.fi==0){
int pos=root2->val.se;
root2->update(pos,pos,INF);
update((pos+1)%n,(pos+n/2)%n,1);
}
root->update(idx,idx,INF);
}
return ans;
}
vector<int> arr;
void init(int k, std::vector<int> r) {
arr=construct_fast(r,k);
//for (auto &it:arr) cout<<it<<" "; cout<<endl;
}
int compare_plants(int x, int y) {
if (arr[x]<arr[y]) return -1;
else return 1;
}
