#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
int n, k, x, y, subtask_id;
vector<int>a;
namespace sub1{
vector<int>f;
void init(){
f = a;
for(int i = 1; i <= n; i++){
f.push_back(f[i]);
}
for(int i = 1; i <= (n << 1); i++){
f[i] += f[i - 1];
}
}
int solve(){
int s = f[y - 1] - f[x - 1];
if(s == 0){
return 1;
}
if(s == y - x){
return -1;
}
if((s = f[x + n - 1] - f[y - 1]) == 0){
return -1;
}
return s == n - y + x ? 1 : 0;
}
}
namespace sub2{
vector<int>pos;
void init(){
pos.resize(n + 1);
vector<int>f(n << 1 | 1);
auto get = [&] (int l, int r){
if(l < 1){
l += n;
}
return f[l > r ? r + n : r] - f[l - 1];
};
for(int z = f[0] = 0; z < n; z++){
for(int i = 1; i <= n; i++){
f[i] = f[i + n] = a[i] == 0;
}
for(int i = 1; i <= (n << 1); i++){
f[i] += f[i - 1];
}
int p = -1;
for(int i = 1; i <= n; i++){
if(a[i] == 0 && get(i - k + 1, i == 1 ? n : i - 1) == 0){
p = i;
break;
}
}
pos[p] = z;
for(int i = p - k + 1; i < p; i++){
a[i < 1 ? i + n : i]--;
}
a[p] = n;
}
}
int solve(){
return pos[x] > pos[y] ? -1 : 1;
}
}
namespace sub5{
const int lim = 305;
bitset<lim>d[lim];
void init(){
for(int i = 1; i <= n; i++){
d[i].reset();
d[i][i] = true;
}
vector<int>f(n << 1 | 1);
auto get = [&] (int l, int r){
if(l < 1){
l += n;
}
return f[l > r ? r + n : r] - f[l - 1];
};
vector<int>order;
for(int z = f[0] = 0; z < n; z++){
for(int i = 1; i <= n; i++){
f[i] = f[i + n] = a[i] == 0;
}
for(int i = 1; i <= (n << 1); i++){
f[i] += f[i - 1];
}
int p = -1;
for(int i = 1; i <= n; i++){
if(a[i] == 0 && get(i - k + 1, i == 1 ? n : i - 1) == 0){
p = i;
break;
}
}
for(int i = 1, j = p; i < k; i++){
if(j++ == n){
j = 1;
}
if(!d[j][p]){
d[p][j] = true;
}
}
for(int i = p - k + 1; i < p; i++){
int j = i < 1 ? i + n : i;
if(!d[j][p]){
d[p][j] = true;
}
a[j]--;
}
a[p] = n;
order.push_back(p);
}
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
if(d[order[i]][order[j]]){
d[order[i]] |= d[order[j]];
}
}
}
}
int solve(){
return d[x][y] ? 1 : -int(d[y][x]);
}
}
namespace sub3467{
const int lim = 2e5 + 5;
int z = lim, val[lim << 1], lazy[lim << 2], sma[19][lim << 1], lar[19][lim << 1];
pair<int, int>st[lim << 2];
void build(int id, int l, int r){
if(l == r){
st[id] = make_pair(a[l], l);
return;
}
int m = (l + r) >> 1;
build(id << 1, l, m);
build(id << 1 | 1, m + 1, r);
st[id] = min(st[id << 1], st[id << 1 | 1]);
}
void propagate(int id, int x){
st[id].first += x;
lazy[id] += x;
}
void push_down(int id){
propagate(id << 1, lazy[id]);
propagate(id << 1 | 1, lazy[id]);
lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v, int x){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
propagate(id, x);
return;
}
int m = (l + r) >> 1;
push_down(id);
update(id << 1, l, m, u, v, x);
update(id << 1 | 1, m + 1, r, u, v, x);
st[id] = min(st[id << 1], st[id << 1 | 1]);
}
pair<int, int>get(int id, int l, int r, int u, int v){
if(l > v || r < u){
return make_pair(n, 0);
}
if(u <= l && v >= r){
return st[id];
}
int m = (l + r) >> 1;
push_down(id);
return min(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
}
void play(int p){
while(true){
bool flag = true;
if(p >= k){
pair<int, int>t = get(1, 1, n, p - k + 1, p - 1);
if(t.first == 0){
play(t.second);
flag = false;
}
}
else{
pair<int, int>t = get(1, 1, n, p - k + 1 + n, n);
if(t.first == 0){
play(t.second);
flag = false;
}
if((t = get(1, 1, n, 1, p - 1)).first == 0){
play(t.second);
flag = false;
}
}
if(flag){
break;
}
}
val[p] = z--;
update(1, 1, n, p, p, n);
if(p >= k){
update(1, 1, n, p - k + 1, p - 1, -1);
}
else{
update(1, 1, n, 1, p - 1, -1);
update(1, 1, n, p - k + 1 + n, n, -1);
}
}
void init(){
memset(lazy, 0, sizeof(lazy));
build(1, 1, n);
while(st[1].first == 0){
play(st[1].second);
}
for(int i = n << 1; i > n; i--){
val[i] = val[i - n];
}
set<pair<int, int>>s;
memset(sma, 0, sizeof(sma));
memset(lar, 0, sizeof(lar));
for(int i = 1, j = 1; i <= (n << 1); i++){
while(j <= (n << 1) && j - i < k){
s.insert(make_pair(val[j], j));
j++;
}
s.erase(make_pair(val[i], i));
auto it = s.lower_bound(make_pair(val[i], i));
if(it != s.end()){
lar[0][i] = it->second;
}
if(it != s.begin()){
sma[0][i] = prev(it)->second;
}
}
for(int i = 1; i < 19; i++){
for(int j = n << 1; j > 0; j--){
sma[i][j] = sma[i - 1][sma[i - 1][j]];
lar[i][j] = lar[i - 1][lar[i - 1][j]];
}
}
}
bool smaller(int x, int y){
for(int i = 18; i > -1; i--){
int nx = lar[i][x];
if(nx != 0 && nx <= y){
x = nx;
}
}
return y - x < k && val[x] <= val[y];
}
bool larger(int x, int y){
for(int i = 18; i > -1; i--){
int nx = sma[i][x];
if(nx != 0 && nx <= y){
x = nx;
}
}
return y - x < k && val[x] >= val[y];
}
int solve(){
return smaller(x, y) || larger(y, x + n) ? -1 : int(larger(x, y) || smaller(y, x + n));
}
}
void init(int _k, vector<int>_a){
swap(a, _a);
n = a.size();
a.insert(a.begin(), 0);
if((k = _k) == 2){
sub1::init();
subtask_id = 1;
}
else if(n <= 5000 && (k << 1) > n){
sub2::init();
subtask_id = 2;
}
else if(n <= 300){
sub5::init();
subtask_id = 5;
}
else{
sub3467::init();
subtask_id = 7;
}
}
int compare_plants(int _x, int _y){
x = _x + 1;
y = _y + 1;
if(subtask_id == 1){
return sub1::solve();
}
if(subtask_id == 2){
return sub2::solve();
}
if(subtask_id == 5){
return sub5::solve();
}
return sub3467::solve();
}
