#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
const int mx = 200005;
int k;
vi r;
int n;
pi rangs[mx][2];
void doK2Init(){
int start = 0;
for(int i = 0; i < n; i++){
if(r[i] != r[0]){
start = i;
break;
}
}
int cur = start;
while(true){
int end_ind = cur;
while(r[(end_ind+1) % n] == r[cur]){
end_ind = (end_ind+1) % n;
}
pi interval = mp(cur, (end_ind+1) % n);
// cout << cur << " " << end_ind << "\n";
// cout << interval.f << " " << interval.s << "\n";
for(int i = cur; ; (i = (i+1) % n)){
if(i == cur){
rangs[i][1] = mp(r[cur], interval.s);
}
else if(i == (end_ind+1) % n){
rangs[i][0] = mp(r[cur], interval.f);
break;
}
else{
rangs[i][0] = mp(r[cur], interval.f);
rangs[i][1] = mp(r[cur], interval.s);
}
}
cur = (end_ind+1) % n;
if(cur == start) break;
}
return;
}
int val[mx];
void init(int _k, vi _r) {
k = _k;
r = _r;
n = sz(r);
if(k == 2){
doK2Init();
return;
}
for(int i = 0; i < n; i++){
val[i] = -1;
}
for(int i = n-1; i >= 0; i--){
int cur_pos = -1;
for(int j = 0; j < n; j++){
if(val[j] != -1) continue;
if(r[j] == 0){
if(cur_pos == -1){
cur_pos = j;
}
else{
if((n+j-cur_pos)*2 < n){
cur_pos = j;
}
}
}
}
assert(cur_pos != -1);
val[cur_pos] = i;
for(int j = 1; j <= k-1; j++){
r[(cur_pos-j+n) % n]--;
}
}
}
bool isInInterval(int test, int int_beg, int int_end){
if(int_beg <= int_end){
return (int_beg <= test) && (test <= int_end);
}
return (int_beg <= test) || (test <= int_end);
}
int doK2Compare(int x, int y){
if(isInInterval(y, rangs[x][0].s, x)){
if(rangs[x][0].f == 1){
return 1;
}
else{
return -1;
}
}
else if(isInInterval(y, x, rangs[x][1].s)){
if(rangs[x][1].f == 1){
return -1;
}
else{
return 1;
}
}
return 0;
}
int compare_plants(int x, int y) {
if(k == 2){
return doK2Compare(x, y);
}
if(val[x] < val[y]) return -1;
return 1;
}
