#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct E {
ll x = 1e15, lz=0;
E(){};
E(ll xx){x=xx;};
friend E operator+(E a, E b){
return min(a.x, b.x);
}
void aply(ll add){
x+=add;
lz+=add;
}
};
struct node{
int lb, rb;
E x;
node *l=nullptr, *r=nullptr;
bool ext(){
if(lb<rb and not l){
int mb = (lb + rb) / 2;
l = new node{lb, mb}, r = new node{mb+1, rb};
}
// push
if(l){
l->x.aply(x.lz);
r->x.aply(x.lz);
x.lz=0;
}
return l;
}
E qry(int lo, int hi){
if(hi<lb or rb<lo) return E();
if(lo<=lb and rb<=hi) return x;
if(ext()) {
E y = l->qry(lo, hi) + r->qry(lo, hi);
return y;
}
return E();
}
void upd(int lo, int hi, ll add){
if(hi<lb or rb<lo) return;
if(lo<=lb and rb<=hi) {
x.aply(add);
return;
}
if(ext()) {
l->upd(lo, hi, add), r->upd(lo, hi, add);
x = l->x + r->x;
}
}
int find(){
if(x.x!=0) return -1;
if(lb==rb) return lb;
ext();
if(l->x.x==0) return l->find();
else return r->find();
}
void bld(vector<int> &v){
if(lb==rb) x.x = v[lb];
if(ext()) {
l->bld(v), r->bld(v);
x = l->x + r->x;
}
}
};
int N, K;
vector<int> topoSort(vector<int> r, int min = 1){
node seg{0, r.size()-1};
seg.bld(r);
vector<int> h(r.size());
deque<int> todo;
for(int i=0; i<r.size(); i++){
int id = seg.find();
while(id==-1){
seg.upd(todo.front(), r.size()-1, -1);
todo.pop_front();
id = seg.find();
}
h[id]=i * min;
seg.upd(id, id, 1e9);
seg.upd(max(0, id - K + 1), id-1, -1);
if(id - K + 1 < 0){
todo.push_back(r.size() - (id - K + 1));
}
}
return h;
}
vector<int> minord, maxord;
void init(int k, std::vector<int> r) {
N = r.size();
K = k;
for(int i=0; i<N; i++) r.push_back(r[i]);
for(auto x:r) cerr<<x<<" "; cerr<<endl;
minord = topoSort(r);
for(auto &x:r) x = K - x - 1;
for(auto x:r) cerr<<x<<" "; cerr<<endl;
maxord = topoSort(r);
for(auto x:minord) cerr<<x<<" "; cerr<<endl;
for(auto x:maxord) cerr<<x<<" "; cerr<<endl;
}
int compare_plants(int x, int y) {
if(minord[x]>minord[y] || maxord[y] > maxord[x + N]) return -1;
if(maxord[x]>maxord[y] || minord[y] > minord[x + N]) return 1;
return 0;
}
