#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
class SegmentTree{
public:
int n;
vector<int> st, lazy;
void build(int i, int l, int r, vector<int>& a){
if(l == r){
st[i] = a[l];
} else{
int m = (l + r) / 2;
build(2*i+1, l, m, a);
build(2*i+2, m+1, r, a);
st[i] = min(st[2*i+1], st[2*i+2]);
}
}
void build(int sz, vector<int>& a){
n = sz;
st.resize(4 * n, n+1);
lazy.resize(4 * n, 0);
build(0, 0, n - 1, a);
}
void push(int i){
if(lazy[i] != 0){
lazy[2*i+1] += lazy[i];
st[2*i+1] += lazy[i];
lazy[2*i+2] += lazy[i];
st[2*i+2] += lazy[i];
}
lazy[i] = 0;
}
int ask(int i, int l, int r, int ql, int qr){
if(qr < l || ql > r || st[i] != 0){
return -1;
}
if(l == r){
return l;
}
push(i);
int m = (l + r) / 2;
int res = -1;
if(res == -1){
res = ask(2*i+1, l, m, ql, qr);
}
if(res == -1){
res = ask(2*i+2, m + 1, r, ql, qr);
}
st[i] = min(st[2*i+1], st[2*i+2]);
return res;
}
int ask(int l, int r){
int res = ask(0, 0, n - 1, l, r);
return res;
}
void add(int i, int l, int r, int ql, int qr){
if(qr < l || ql > r){
return;
}
if(ql <= l && r <= qr){
st[i]--;
lazy[i]--;
return;
}
push(i);
int m = (l + r) / 2;
add(2*i+1, l, m, ql, qr);
add(2*i+2, m+1, r, ql, qr);
st[i] = min(st[2*i+1], st[2*i+2]);
}
void add(int l, int r){
add(0, 0, n - 1, l, r);
}
void pop(int i, int l, int r, int p, int k){
if(l == r){
st[i] = k;
return;
}
push(i);
int m = (l + r) / 2;
if(p <= m)
pop(2*i+1, l, m, p, k);
else
pop(2*i+2, m+1, r, p, k);
st[i] = min(st[2*i+1], st[2*i+2]);
}
void pop(int i, int k){
pop(0, 0, n-1, i, k);
}
};
int N, K;
vector<int> P, R;
SegmentTree st;
int ask(int l, int r){
return st.ask(l, r);
/*
for(int i = l; i <= r; i++){
if(R[i] == 0)
return i;
}
return -1;
*/
}
void pop(int i){
st.pop(i, N);
}
void add(int l, int r){
st.add(l, r);
/*
for(int i = l; i <= r; i++){
R[i]--;
}
*/
}
void f(int& n, int pos){
int pos2;
while(true){
pos2 = -1;
int l = pos - K + 1, r = pos - 1;
if(r < 0){
l += N, r += N;
pos2 = ask(l, r);
} else if(l < 0){
l += N;
pos2 = max(ask(0, r), ask(l, N-1));
} else{
pos2 = ask(l, r);
}
if(pos2 == -1){
break;
}
f(n, pos2);
}
P[pos] = n--;
pop(pos);
int l = pos - K + 1, r = pos - 1;
if(r < 0){
l += N, r += N;
add(l, r);
} else if(l < 0){
l += N;
add(0, r);
add(l, N-1);
} else{
add(l, r);
}
}
void genera(){
int n = N;
while(n >= 0){
int pos = ask(0, N-1);
f(n, pos);
}
}
vector<vector<int>> g, g2;
vector<vector<bool>> vis[2];
void bfs(int s){
queue<int> q;
q.push(s);
while(!q.empty()){
int v = q.front();
q.pop();
for(auto u : g[v]){
if(vis[0][s][u] == false){
vis[0][s][u] = true;
q.push(u);
}
}
}
q.push(s);
while(!q.empty()){
int v = q.front();
q.pop();
for(auto u : g2[v]){
if(vis[1][s][u] == false){
vis[1][s][u] = true;
q.push(u);
}
}
}
}
void init(int k, vector<int> r){
N = SZ(r), K = k, R = r;
P.resize(N);
st.build(N, r);
genera();
if(N <= 300){
g.resize(N);
g2.resize(N);
vis[0].resize(N);
vis[1].resize(N);
for(int i = 0; i < N; i++){
vis[0][i].resize(N, false);
vis[1][i].resize(N, false);
for(int j = i + 1; j <= i + K - 1; j++){
if(P[i] > P[j % N]){
g[i].pb(j % N);
g2[j % N].pb(i);
} else{
g[j % N].pb(i);
g2[i].pb(j % N);
}
}
}
for(int i = 0; i < N; i++){
bfs(i);
}
}
}
int compare_plants(int x, int y){
if(N <= 300){
if(vis[0][x][y] || vis[1][y][x])
return 1;
if(vis[1][x][y] || vis[0][y][x])
return -1;
return 0;
}
if(P[x] > P[y])
return 1;
if(P[x] < P[y])
return -1;
return 0;
}
/*
static int n, k, q;
static std::vector<int> r;
static std:: vector<int> x;
static std:: vector<int> y;
static std:: vector<int> answer;
int main() {
assert(scanf("%d%d%d", &n, &k, &q) == 3);
r.resize(n);
answer.resize(q);
for (int i = 0; i < n; i++) {
int value;
assert(scanf("%d", &value) == 1);
r[i] = value;
}
x.resize(q);
y.resize(q);
for (int i = 0; i < q; i++) {
assert(scanf("%d%d", &x[i], &y[i]) == 2);
}
fclose(stdin);
init(k, r);
for (int i = 0; i < q; i++) {
answer[i] = compare_plants(x[i], y[i]);
}
for (int i = 0; i < q; i++) {
printf("%d\n", answer[i]);
}
fclose(stdout);
return 0;
}
*/
