#include "plants.h"
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define ln "\n"
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()
constexpr ll inf = (1ll<<60);
template<typename T = pii, typename S = ll>
struct lazy_segment_tree{
int N, log;
T valINF;
S lazyINF;
vector<T> node;
vector<S> lazy;
lazy_segment_tree(int n, T valINF_, S lazyINF_): valINF(valINF_), lazyINF(lazyINF_){
N = 1;
log = 1;
while(N <= n){
N *= 2;
log++;
}
node.resize(2*N, valINF);
lazy.resize(2*N, lazyINF);
}
void init(vector<T> a){
rep(i,0,a.size()) node[i+N] = a[i];
per(i,N-1,1) node[i] = compare(node[i*2], node[i*2+1]);
}
void range_add(S val, ll a, ll b, ll now = 1, ll l = 0, ll r = -1){
if(r == -1) r = N;
eval(now);
if(r <= a || b <= l) return;
if(a <= l && r <= b){
addition(lazy[now], val);
eval(now);
return;
}
range_add(val, a, b, now*2, l, (l+r)/2);
range_add(val, a, b, now*2+1, (l+r)/2, r);
node[now] = compare(node[now*2], node[now*2+1]);
}
T calc(ll a, ll b, ll now = 1, ll l = 0, ll r = -1){
if(r == -1) r = N;
eval(now);
if(r <= a || b <= l) return valINF;
if(a <= l && r <= b) return node[now];
T L = calc(a, b, now*2, l, (l+r)/2);
T R = calc(a, b, now*2+1, (l+r)/2, r);
return compare(L,R);
}
void update(ll idx, T val){
ll now = idx+N;
per(i,log,0){
eval(now>>i);
}
node[now] = val;
now /= 2;
while(now){
eval(now*2);
eval(now*2+1);
node[now] = compare(node[now*2], node[now*2+1]);
now /= 2;
}
}
void eval(ll now){
addition(node[now], lazy[now]);
if(now < N){
addition(lazy[now*2], lazy[now]);
addition(lazy[now*2+1], lazy[now]);
}
lazy[now] = lazyINF;
}
void addition(T &a, S b){
a.first += b;
}
void addition(S &a, S b){
a += b;
}
T compare(T a, T b){
return std::min(a, b);
}
};
ll N;
vi height;
void subtask_2_3(int k, vector<int> r){
N = r.size();
lazy_segment_tree<pii, ll> seg(N, mp(inf,0), 0);
{
vector<pii> a(N);
rep(i,0,N) a[i] = mp(r[i], i);
seg.init(a);
}
height.resize(N);
ll now = N;
std::set<ll> cand;
std::set<ll> top;
auto check = [&](ll idx){
auto itr = cand.lower_bound(idx);
itr--;
ll right = idx+k-1;
right -= N;
if(*itr <= right) return true;
else return false;
};
while(true){
while(true){
auto el = seg.calc(0,N);
if(el.first) break;
ll i = el.second;
cand.insert(i);
cand.insert(i-N);
cand.insert(i+N);
if(check(i)) top.insert(i);
if(cand.size() > 3){
ll upper = *cand.upper_bound(i);
if(upper >= N) upper -= N;
if(top.count(upper)){
if(!check(upper)) top.erase(upper);
}
}
seg.update(i,mp(inf, 0));
}
if(cand.empty()) break;
assert(top.size() == 1);
ll t = *top.begin();
height[t] = now--;
{
ll l = t-k+1;
ll r = t;
if(0 <= l) seg.range_add(-1, l, r);
else{
seg.range_add(-1, 0, r);
seg.range_add(-1, N+l, N);
}
}
cand.erase(t);
cand.erase(t-N);
cand.erase(t+N);
top.erase(t);
if(cand.empty()) continue;
ll upper = *cand.upper_bound(t);
if(upper >= N) upper -= N;
if(check(upper)) top.insert(upper);
}
/*while((seg.calc(0,N)).first == 0){
vi idx;
while(true){
auto el = seg.calc(0,N);
if(el.first) break;
idx.pb(el.second);
seg.update(el.second, mp(inf, 0));
}
if(idx.size() == 1){
height[idx[0]] = now--;
ll l = idx[0]-k+1;
ll r = idx[0];
if(0 <= l) seg.range_add(-1, l, r);
else{
seg.range_add(-1, 0, r);
seg.range_add(-1, N+l, N);
}
continue;
}
assert(idx.size() == 2);
if(idx[0] > idx[1]) std::swap(idx[0], idx[1]);
if(idx[1] < idx[0]+k){
idx[0] = now--;
idx[1] = now--;
}
else{
idx[1] = now--;
idx[0] = now--;
}
rep(i,0,2){
ll l = idx[i]-k+1;
ll r = idx[i];
if(0 <= l) seg.range_add(-1, l, r);
else{
seg.range_add(-1, 0, r);
seg.range_add(-1, N+l, N);
}
}
}*/
/*rep(i,0,N) cout << height[i] << " ";
cout << ln;*/
}
vii edge;
void subtask_5(int k, std::vector<int> r){
N = r.size();
edge.resize(N,vi(N));
vector<bool> flag(N);
rep(_,0,N){
ll top = -1;
rep(i,0,N){
if(r[i]) continue;
ll now = i;
bool f = true;
rep(j,1,k){
now--;
if(now < 0) now += N;
if(r[now]) continue;
f = false;
}
if(f) top = i;
}
flag[top] = true;
/*cout << top << ln;
rep(i,0,N) cout << r[i] << " ";
cout << ln;*/
ll now = top;
rep(j,1,k){
now++;
now %= N;
if(flag[now]) continue;
edge[top][now] = true;
}
now = top;
rep(j,1,k){
now--;
if(now < 0) now += N;
r[now]--;
if(flag[now]) continue;
edge[top][now] = true;
}
r[top] = 1e9;
}
rep(k,0,N){
rep(i,0,N){
rep(j,0,N){
edge[i][j] |= (edge[i][k]&edge[k][j]);
}
}
}
}
vii par;
vector<int> r_mem;
void subtask_1(int k, std::vector<int> r){
N = r.size();
par.resize(N);
rep(i,0,N){
if(r[i] == 0){
par[(i+1)%N].pb(i);
}
else{
par[i].pb((i+1)%N);
}
}
r_mem = r;
}
void init(int k, std::vector<int> r) {
N = r.size();
if(N <= 300) subtask_5(k,r);
else if(2*k > N) subtask_2_3(k,r);
else subtask_1(k,r);
}
int compare_plants(int x, int y) {
if(!height.empty()){
if(height[x] < height[y]) return -1;
else return 1;
}
else if(!edge.empty()){
if(edge[x][y]) return 1;
else if(edge[y][x]) return -1;
else return 0;
}
else{
std::function<ll(ll)> root = [&](ll now){
if(par[now].empty()) return now;
return par[now][0] = root(par[now][0]);
};
if(par[x].size() == 2 && par[y].size() == 2) return 0;
if(par[x].empty() && par[y].empty()) return 0;
if(par[x].size() == 2){
if(root(par[x][0]) == root(y)) return -1;
if(root(par[x][1]) == root(y)) return -1;
return 0;
}
if(par[y].size() == 2){
if(root(par[y][0]) == root(x)) return 1;
if(root(par[y][1]) == root(x)) return 1;
return 0;
}
if(root(x) != root(y)) return 0;
if(r_mem[x] == 0 && r_mem[(y+N-1)%N] == 0) return 1;
if(r_mem[y] == 0 && r_mem[(x+N-1)%N] == 0) return -1;
if(r_mem[x] == 1 && r_mem[(y+1)%N] == 1) return -1;
if(r_mem[y] == 1 && r_mem[(x+1)%N] == 1) return 1;
}
}
