#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MN = 100010;
int N, K, Q;
int L[MN];
vector<int> V[MN];
map<pii, vector<int> > ldist, rdist;
struct BIT {
vector<int> tree;
void init() {
tree = vector<int>(4 * N, -1e9);
}
void upd(int x, int v, int l, int r, int n) {
if(x < l || r < x) return;
if(l == r) {
tree[n] = v;
return;
}
int m = (l + r)>>1;
upd(x, v, l, m, 2*n);
upd(x, v, m + 1, r, 2*n + 1);
tree[n] = max(tree[2*n], tree[2*n + 1]);
}
int quer(int a, int b, int l, int r, int n) {
if(b < l || r < a) return -1e9;
if(a <= l && r <= b) return tree[n];
int m = (l + r)>>1;
int L = quer(a, b, l, m, 2*n);
int R = quer(a, b, m + 1, r, 2*n + 1);
return max(L, R);
}
} bit, sub1, sub2;
void solve(int l, int r) {
if(l + 1 == r) {
ldist[ pii(l, r) ] = vector<int>(r - l + 1, 0);
rdist[ pii(l, r) ] = vector<int>(r - l + 1, 0);
ldist[ pii(l, r) ][1] = 1;
rdist[ pii(l, r) ][1] = 1;
return;
}
int x = bit.quer(l + 1, r - 1, 0, N - 1, 1);
int a = lower_bound(V[x].begin(), V[x].end(), l) - V[x].begin();
vector<int> P;
P.push_back(l);
for(int i = a; i < V[x].size() && V[x][i] < r; i++) P.push_back(V[x][i]);
P.push_back(r);
ldist[ pii(l, r) ] = vector<int>(r - l + 1, 0);
rdist[ pii(l, r) ] = vector<int>(r - l + 1, 0);
for(int i = 0; i < (int)P.size() - 1; i++) {
solve(P[i], P[i + 1]);
for(int j = P[i]; j <= P[i + 1]; j++) {
int d1 = i + ldist[ pii(P[i], P[i + 1]) ][ j - P[i] ];
int d2 = (int)P.size() - 2 - i + rdist[ pii(P[i], P[i + 1]) ][ P[i + 1] - j ];
ldist[ pii(l, r) ][j - l] = min(d1, d2 + 1);
rdist[ pii(l, r) ][r - j] = min(d1 + 1, d2);
}
}
}
struct Query {
int a, b, id;
};
vector<Query> query[MN];
int ans[MN];
int main() {
scanf("%d %d %d", &N, &K, &Q);
for(int i = 0; i < N; i++) {
scanf("%d", &L[i]);
V[ --L[i] ].push_back(i);
}
bit.init();
for(int i = 0; i < N; i++) bit.upd(i, L[i], 0, N - 1, 1);
for(int i = 0; i < (int)V[K - 1].size() - 1; i++) {
solve(V[K - 1][i], V[K - 1][i + 1]);
}
for(int i = 0; i < Q; i++) {
int a, b; scanf("%d %d", &a, &b);
a--; b--;
if(a > b) swap(a, b);
int x = bit.quer(a, b, 0, N - 1, 1);
query[x].push_back({ a, b, i });
}
sub1.init();
sub2.init();
for(int i = K - 1; i >= 0; i--) {
for(int j = 0; j < query[i].size(); j++) {
int a = query[i][j].a;
int b = query[i][j].b;
int id = query[i][j].id;
int l = lower_bound(V[i].begin(), V[i].end(), a) - V[i].begin();
int r = upper_bound(V[i].begin(), V[i].end(), b) - V[i].begin() - 1;
int pl = sub1.quer(0, a, 0, N - 1, 1);
int pr = -sub2.quer(b, N - 1, 0, N - 1, 1);
ans[id] = 1e9;
if(pl != -1e9 && pr != 1e9) ans[id] = min(ans[id], ldist[ pii(pl, pr) ][a - pl] + rdist[ pii(pl, pr) ][pr - b] + 1);
int d1, d2;
if(a == V[i][l]) d1 = 0;
else {
if(l) pl = max(pl, V[i][l - 1]);
d1 = rdist[ pii(pl, V[i][l]) ][ V[i][l] - a ];
}
if(b == V[i][r]) d2 = 0;
else {
if(r < (int)V[i].size() - 1) pr = min(pr, V[i][r + 1]);
d2 = ldist[ pii(V[i][r], pr) ][ b - V[i][r] ];
}
ans[id] = min(ans[id], d1 + d2 + r - l);
}
for(int j = 0; j < V[i].size(); j++) {
int x = V[i][j];
sub1.upd(x, x, 0, N - 1, 1);
sub2.upd(x, -x, 0, N - 1, 1);
}
}
for(int i = 0; i < Q; i++) {
printf("%d\n", ans[i] - 1);
}
}
