#include "plants.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= l; --x)
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;
const int N = 200'010;
vector<int> A[N];
int val[N], pos[N];
int n, k;
namespace seg1 {
int a[2*N];
void init() { fill(a, a+2*N, N); }
void up(int p, int x) {
p += N;
while (p > 0) {
a[p] = x;
p /= 2;
}
}
int get(int l, int r) {
l += N;
r += N;
int ans = N;
while (l < r) {
if (l&1) ans = min(ans, a[l++]);
if (r&1) ans = min(ans, a[--r]);
l /= 2;
r /= 2;
}
return ans;
}
int getc(int l, int r) {
--r;
l = (l%n+n)%n;
r = (r%n+n)%n;
++r;
if (l >= r)
return min(get(0, r), get(l, n));
else
return get(l, r);
}
}
void init(int k, std::vector<int> r) {
::k = k;
n = r.size();
LoopR (x,0,n) {
vector<int> z;
Loop (i,0,n) {
if (r[i] == 0)
z.push_back(i);
}
int p = -1;
Loop (i,0,z.size()) {
if (z[i] - (i == 0? z.back() - n: z[i-1]) >= k) {
p = z[i];
break;
}
}
assert(p != -1);
Loop (ii,p-k+1,p) {
int i = (ii+n)%n;
if (r[i] != -1)
r[i]--;
}
r[p] = -1;
val[p] = x;
pos[x] = p;
}
seg1::init();
LoopR (i,0,n) {
int l = seg1::getc(pos[i]-k+1, pos[i]);
int r = seg1::getc(pos[i]+1, pos[i]+k);
if (l != N)
A[pos[i]].push_back(pos[l]);
if (r != N)
A[pos[i]].push_back(pos[r]);
seg1::up(pos[i], i);
}
//int mx = 0;
//while (val[mx] != n-1)
// ++mx;
//vector<int> vec = {mx};
//Loop (ii,mx+1,mx+n) {
// int i = ii%n;
// while (val[vec.back()] < val[i])
// vec.pop_back();
// A[i].push_back(vec.back());
// vec.push_back(i);
//}
//vec = {mx};
//LoopR (ii,mx-n+1,mx) {
// int i = (ii+n)%n;
// while (val[vec.back()] < val[i])
// vec.pop_back();
// A[i].push_back(vec.back());
// vec.push_back(i);
//}
}
bool vis[N];
bool dfs(int v, int dst)
{
if (v == dst)
return 1;
vis[v] = 1;
for (int u : A[v]) {
if (!vis[u] && dfs(u, dst))
return 1;
}
return 0;
}
int compare_plants(int x, int y) {
//if (val[x] > val[y])
// return 1;
//else
// return -1;
memset(vis, 0, n);
if (dfs(x, y))
return -1;
memset(vis, 0, n);
if (dfs(y, x))
return 1;
return 0;
}
