#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
vector<int> h;
const int inf = 1e9;
class segment_tree{
public:
pair<int, int> id_max(){ return seg[1].maxi; }
void update( int l, int r, int val ){ update( 1, 0, n - 1, l, r, val ); }
segment_tree( vector<int>& v, int k ): n(v.size()), k(k) { seg.resize(4*v.size()); build( 1, 0, n - 1, v ); }
private:
int n, k;
struct Node{
pii maxi;
int lazy = 0, aux = 0;
Node( pii maxi = pii(0, 0), int k = 0 ) : maxi(maxi), aux(k) {}
Node operator + ( Node n ) const {
if( maxi.first > n.maxi.first ) return *this;
if( maxi.first < n.maxi.first ) return n;
if( maxi.second + aux - 1 >= n.maxi.second ) return *this;
return n;
}
};
vector<Node> seg;
void build( int pos, int ini, int fim, vector<int>& v ){
if( ini == fim ){ seg[pos] = Node( pii( v[ini], ini ), k ); return; }
int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
build( l, ini, mid, v ); build( r, mid + 1, fim, v );
seg[pos] = seg[l] + seg[r];
}
void refresh( int pos, int ini, int fim ){
if( seg[pos].lazy == 0 ) return;
int x = seg[pos].lazy; seg[pos].lazy = 0;
seg[pos].maxi.first += x;
if( ini == fim ) return;
seg[2*pos].lazy += x;
seg[2*pos + 1].lazy += x;
}
void update( int pos, int ini, int fim, int ki, int kf, int val ){
refresh( pos, ini, fim );
if( ki > fim || ini > kf ) return;
if( ki <= ini && fim <= kf ){
seg[pos].lazy += val; refresh( pos, ini, fim );
return;
}
int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
update( l, ini, mid, ki, kf, val ); update( r, mid + 1,fim, ki, kf, val );
seg[pos] = seg[l] + seg[r];
}
};
void init(int k, vector<int> r) {
int n = r.size();
segment_tree seg(r, k);
h.resize(n);
for( int i = 0; i < n; i++ ){
vector<int> v;
while( seg.id_max().first == k - 1 ){
int id = seg.id_max().second;
v.push_back(id);
seg.update( id, id, -inf );
seg.update( id + 1, id + k - 1, -inf );
if( id + k - 1 >= n ) seg.update( 0, id + k - 1 - n, -inf );
h[id] = i;
}
for( int x : v ){
seg.update( x + 1, x + k - 1, inf );
if( x + k - 1 >= n ) seg.update( 0, x + k - 1 - n, inf );
seg.update( x - k + 1, x - 1, 1 );
if( x - k + 1 < 0 ) seg.update( n + x - k + 1, n - 1, 1 );
}
}
return;
}
int compare_plants(int x, int y) {
if( h[x] < h[y] ) return -1;
if( h[x] > h[y] ) return 1;
return 0;
}
