#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#ifndef WAIMAI
#include "plants.h"
#endif
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
#define lpos pos*2
#define rpos pos*2+1
const int INF = 1e9;
const int SIZE = 2e5 + 5;
int n, k;
int a[SIZE], p[SIZE];
vector<int> adj[SIZE];
vector<pair<int, int>> g[SIZE];
set<int> s;
set<pair<int, int>> d;
int dis(int l, int r) {
return l < r ? r - l : r + n - l;
}
void add(int i) {
if (s.size() == 0) {
s.insert(i);
d.emplace(n, i);
return;
}
auto it = s.lower_bound(i);
int L = (it == s.begin() ? *s.rbegin() : *prev(it));
int R = (it == s.end() ? *s.begin() : *it);
//debug("add", i, L, R);
d.erase({dis(L, R), R});
d.emplace(dis(L, i), i);
d.emplace(dis(i, R), R);
s.insert(i);
}
void del(int i) {
//debug("del", i);
//for (int x : s) cout << x << ' '; cout << '\n';
//for (auto [de, i] : d) debug(de, i);
if (s.size() == 1) {
s.clear();
d.clear();
return;
}
auto it = s.lower_bound(i);
int L = (it == s.begin() ? *s.rbegin() : *prev(it));
int R = (next(it) == s.end() ? *s.begin() : *next(it));
s.erase(it);
d.erase({dis(L, i), i});
d.erase({dis(i, R), R});
d.emplace(dis(L, R), R);
//for (int x : s) cout << x << ' '; cout << '\n';
//for (auto [de, i] : d) debug(de, i); cout << "----\n";
}
int mn[SIZE * 4], lazy[SIZE * 4];
void push(int pos, int l, int r) {
mn[pos] += lazy[pos];
if (l < r) {
lazy[lpos] += lazy[pos];
lazy[rpos] += lazy[pos];
}
lazy[pos] = 0;
}
void pull(int pos, int l, int r) {
int mid = (l + r) / 2;
push(lpos, l, mid);
push(rpos, mid + 1, r);
mn[pos] = min(mn[lpos], mn[rpos]);
}
void build(int pos, int l, int r) {
if (l == r) {
mn[pos] = k - 1 - a[l];
return;
}
int mid = (l + r) / 2;
build(lpos, l, mid);
build(rpos, mid + 1, r);
mn[pos] = min(mn[lpos], mn[rpos]);
}
void upd(int pos, int l, int r, int L, int R, int x) {
if (l == L && r == R) {
lazy[pos] += x;
return;
}
push(pos, L, R);
int mid = (L + R) / 2;
if (r <= mid) upd(lpos, l, r, L, mid, x);
else if (l > mid) upd(rpos, l, r, mid + 1, R, x);
else {
upd(lpos, l, mid, L, mid, x);
upd(rpos, mid + 1, r, mid + 1, R, x);
}
pull(pos, L, R);
}
void dfs(int pos, int l, int r) {
push(pos, l, r);
if (mn[pos] != 0) return;
if (l == r) {
add(l);
mn[pos] += INF;
return;
}
int mid = (l + r) / 2;
dfs(lpos, l, mid);
dfs(rpos, mid + 1, r);
pull(pos, l, r);
}
void init(int _k, vector<int> r) {
n = r.size();
k = _k;
FOR (i, 0, n - 1) a[i] = r[i], p[i] = -1;
if (k == 2) {
FOR (i, 0, n - 1) {
if (a[i] == 1) adj[i].pb((i + 1) % n);
else adj[(i + 1) % n].pb(i);
}
int sz = 0;
FOR (i, 0, n - 1) if (adj[i].size() == 2) {
for (int x : adj[i]) {
int cnt = 0;
g[i].pb(sz, cnt++);
while (adj[x].size()) {
g[x].pb(sz, cnt++);
x = adj[x][0];
}
g[x].pb(sz, cnt++);
sz++;
}
}
return;
}
build(1, 0, n - 1);
FOR (i, 0, n - 1) {
dfs(1, 0, n - 1);
/*if (!d.size()) {
cout << "qq\n";
exit(0);
}*/
auto [ld, j] = *d.rbegin();
assert(d.size() && ld >= k);
//debug(ld, j);
del(j);
p[j] = i;
int l = j - k + 1, r = j - 1;
if (l < 0) l += n;
if (r < 0) r += n;
if (l <= r) upd(1, l, r, 0, n - 1, -1);
else {
upd(1, l, n - 1, 0, n - 1, -1);
upd(1, 0, r, 0, n - 1, -1);
}
}
}
int compare_plants(int x, int y) {
if (k == 2) {
for (auto [gx, px] : g[x]) for (auto [gy, py] : g[y]) if (gx == gy) {
return px < py ? -1 : 1;
}
return 0;
}
return p[x] < p[y] ? -1 : 1;
}
/*
in1
4 3 2
0 1 1 2
0 2
1 2
out1
1
-1
in2
4 2 2
0 1 0 1
0 3
1 3
out2
1
0
ex1(4 1 2 5 3 0)
6 4 5
1 3 2 0 1 3
0 1
3 4
2 0
1 3
5 2
*/
#ifdef WAIMAI
int main() {
int n, k, q;
vector<int> r;
vector<int> x;
vector<int> y;
vector<int> answer;
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;
}
#endif
