//
#ifndef __SIZEOF_INT128__
#define __SIZEOF_INT128__
#endif
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template <typename T> using oset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define rep(i, p, k) for(int i(p); i < (k); ++i)
#define per(i, p, k) for(int i(p); i > (k); --i)
#define sz(x) (int)(x).size()
#define sc static_cast
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef __int128_t lll;
//#define int ll
template <typename T = int> using par = std::pair <T, T>;
#define fi first
#define se second
#define test int _number_of_tests(in()); while(_number_of_tests--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb emplace_back
struct Timer {
string name{""};
time_point<high_resolution_clock> end, start{high_resolution_clock::now()};
duration<float, std::milli> dur;
Timer() = default;
Timer(string nm): name(nm) {}
~Timer() {
end = high_resolution_clock::now(); dur= end - start;
cout << "@" << name << "> " << dur.count() << " ms" << '\n';
}
};
template <typename T = int> inline T in()
{
static T x;
std::cin >> x;
return x;
}
std::string yn(bool b)
{
if(b) return "YES\n";
else return "NO\n";
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par);
template <typename T> std::ostream& operator<< (std::ostream& out, const std::vector <T>& wek)
{
for(const auto& i : wek)out << i << ' ';
return out;
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par)
{
out << '{'<<par.first<<", "<<par.second<<"}";
return out;
}
#define show(x) cerr << #x << " = " << x << '\n';
#include "plants.h"
constexpr int maxn = 2e5 + 3, maxk = 20, pol = 1<<18;
int ls[maxn][maxk], rs[maxn][maxk], ko[maxn];
ll ld[maxn][maxk], rd[maxn][maxk];
int n;
constexpr int tres = pol*2+3;
struct t2t{
int m, g;
};
t2t operator+(t2t a, t2t b){ return (a.m < b.m) ? b : a; }
t2t t2[tres];
t2t t2s(int a, int b){
t2t o{-1, n};
a += pol-1; b += pol+1;
while(a+1 != b){
if(a % 2 == 0)o = o + t2[a+1];
if(b % 2 == 1)o = o + t2[b-1];
a /= 2; b /= 2;
}
return o;
}
void init(int k, vector <int> r)
{
n = sz(r);
rep(i, 0, tres)t2[i] = {-1, n};
rep(c, 1, n+1){
int a(-1);
rep(i, 0, n)if(r[i] == 0){
bool b(1);
rep(j, 1, k)b &= !!r[(n+i-j)%n];
if(b){
a = i;
break;
}
}
rep(j, 1, k)if(r[(n+a-j)%n] > 0) r[(n+a-j)%n]--;
auto [lm, lg] = (a-k+1 >= 0) ? t2s(a-k+1, a-1) : t2s(n+a-k+1, n-1) + t2s(0, a-1);
ls[a][0] = lg;
ld[a][0] = lg == n ? -1 : (n+a-lg)%n;
auto [rm, rg] = (a+k-1 < n) ? t2s(a+1, a+k-1) : t2s(a, n-1) + t2s(0, a+k-1-n);
rs[a][0] = rg;
rd[a][0] = rg == n ? -1 : (n+rg-a)%n;
r[a] = -c;
ko[a] = c;
int t2g(a+pol);
t2[t2g] = {ko[a], a};
while(t2g > 1){
t2g /= 2;
t2[t2g] = t2[t2g*2] + t2[t2g*2+1];
}
}
ko[n] = -1;
ls[n][0] = rs[n][0] = n;
rep(k, 1, maxk)rep(i, 0, n+1){
ls[i][k] = ls[ls[i][k-1]][k-1];
ld[i][k] = ld[i][k-1] + ld[ls[i][k-1]][k-1];
}
rep(k, 1, maxk)rep(i, 0, n+1){
rs[i][k] = rs[rs[i][k-1]][k-1];
rd[i][k] = rd[i][k-1] + rd[rs[i][k-1]][k-1];
}
}
int compare_plants(int x, int y)
{
int m(1);
if(ko[x] > ko[y]){
swap(x, y);
m = -1;
}
int z(y);
ll d(0);
per(k, maxk-1, -1){
while(ko[ls[z][k]] >= ko[x]){
d += ld[z][k];
z = ls[z][k];
}
}
if(x < y){
if(y-d <= x)return m;
}
else{
if(y-d <= x-n)return m;
}
z = y;
d = 0;
per(k, maxk-1, -1){
while(ko[rs[z][k]] >= ko[x]){
d += rd[z][k];
z = rs[z][k];
}
}
if(x < y){
if(y+d >= x+n)return m;
}
else{
if(y+d >= x)return m;
}
return 0;
}
