#include <bits/stdc++.h>
using namespace std;
namespace siuu {
constexpr int maxn = 1e5+10;
int a[maxn], l[maxn], r[maxn], dist[2][maxn];
void bfs(int s, int k) {
for(int i = 0; i < maxn; i++)
dist[k][i] = 0x3f3f3f3f;
dist[k][s] = 0;
queue<int> q;
q.push(s);
while(q.size()) {
int u = q.front(); int d = dist[k][u];
q.pop();
for(int rep = 0; rep < 2; rep++, swap(l[u], r[u]))
if(dist[k][l[u]] > d+1)
q.push(l[u]), dist[k][l[u]] = d+1;
}
}
void brute(int n, int k, int q) {
for(int i = 0; i < n; i++)
scanf("%d", a+i);
l[0] = 0;
for(int i = 1; i < n; i++) {
l[i] = i-1;
while(a[l[i]] < a[i])
l[i] = l[l[i]];
}
r[n-1] = n-1;
for(int i = n-2; i >= 0; i--) {
r[i] = i+1;
while(a[r[i]] < a[i])
r[i] = r[r[i]];
}
while(q--) {
int x, y; scanf("%d %d", &x, &y);
--x, --y;
bfs(x, 0); bfs(y, 1);
int ans = 0x3f3f3f3f;
for(int i = 0; i < n; i++)
ans = min(ans, dist[0][i] + dist[1][i] - 1);
printf("%d\n", ans);
}
}
}
constexpr int maxn = 1e5+10, maxk = 21;
int a[maxn], l[maxn][2], r[maxn][2], dist[2][maxn], mark[maxn], seen[maxn], cnt;
vector<int> pos[maxk];
int d(int x, int y, int k) {
// se x==y ele retorna -1 e é pra retornar isso mesmo
if(x > y) swap(x, y);
return lower_bound(pos[k].begin(), pos[k].end(), y) - lower_bound(pos[k].begin(), pos[k].end(), x) - 1;
}
vector<int> reached[2][maxk];
void dijkstra(int s, int k) {
++cnt;
dist[k][s] = 0;
seen[s] = cnt;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
q.push({0, s});
while(q.size()) {
int u = q.top().second; q.pop();
if(mark[u] == cnt) continue;
mark[u] = cnt;
reached[k][a[u]].push_back(u);
int d = dist[k][u];
for(auto [v, w] : {make_pair(l[u][0], l[u][1]), make_pair(r[u][0], r[u][1])}) {
if(seen[v] < cnt || dist[k][v] > d + w) {
seen[v] = cnt;
dist[k][v] = d+w;
q.push({d+w, v});
}
}
}
}
int main() {
int n, k, q; scanf("%d %d %d", &n, &k, &q);
if(k > 20) return siuu::brute(n, k, q), 0;
for(int i = 0; i < n; i++) {
scanf("%d", a+i);
for(int j = 0; j <= a[i]; j++)
pos[j].push_back(i);
}
for(int i = 0; i < n; i++) {
if(a[i] == k) { l[i][0] = i; l[i][1] = 0; continue; }
l[i][0] = i-1; l[i][1] = 1;
while(a[l[i][0]] <= a[i]) {
l[i][1] = (a[l[i][0]] == a[i] ? l[l[i][0]][1] : 0) + 1;
l[i][0] = l[l[i][0]][0];
}
}
for(int i = n-1; i >= 0; i--) {
if(a[i] == k) { r[i][0] = i, r[i][1] = 0; continue; }
r[i][0] = i+1; r[i][1] = 1;
while(a[r[i][0]] <= a[i]) {
r[i][1] = (a[r[i][0]] == a[i] ? r[r[i][0]][1] : 0) + 1;
r[i][0] = r[r[i][0]][0];
}
}
while(q--) {
int x, y; scanf("%d %d", &x, &y);
--x, --y;
dijkstra(x, 0); dijkstra(y, 1);
int ans = 0x3f3f3f3f;
for(int lvl = 1; lvl <= k; lvl++) {
for(int x : reached[0][lvl]) for(int y : reached[1][lvl])
ans = min(ans, dist[0][x] + dist[1][y] + d(x, y, lvl));
reached[0][lvl].clear(), reached[1][lvl].clear();
}
printf("%d\n", ans);
}
}
