#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair
const int mxn = 1e6 + 10;
int a[mxn], n, k, q;
int mn[mxn], mx[mxn];
vector<int> ind[mxn];
vector<int> adj[mxn];
int fmax(int u) { return mx[u] == u ? u : mx[u] = fmax(mx[u]); }
int fmin(int u) { return mn[u] == u ? u : mn[u] = fmin(mn[u]); }
int dis[mxn];
int djkstra(int st, int en) {
for(int i = 1; i <= n; i++)
dis[i] = -1;
priority_queue<pii> pq;
pq.push(MP(0, st));
while(pq.size()) {
int d = -pq.top().ff;
int u = pq.top().ss;
pq.pop();
if(u == en) return d;
if(dis[u] > -1) continue;
dis[u] = d;
for(int v : adj[u]) {
if(dis[v] == -1)
pq.push(MP(-d - 1, v));
}
}
return -1;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k >> q;
for(int i = 1; i <= n; i++) {
cin >> a[i];
mn[i] = mx[i] = i;
ind[a[i]].push_back(i);
}
mn[n + 1] = mx[n + 1] = 1;
for(int x = 1; x < k; x++) {
for(int i : ind[x]) {
mn[i] = i - 1;
mx[i] = i + 1;
}
int prv = -1;
for(int i : ind[x]) {
if(prv >= i) continue;
int L = fmin(i);
int R = fmax(i);
adj[L].push_back(R);
adj[R].push_back(L);
prv = R;
}
}
for(int i = 1; i < n; i++) {
adj[i].push_back(i + 1);
adj[i + 1].push_back(i);
}
for(int i = 0; i < q; i++) {
int u, v;
cin >> u >> v;
cout << djkstra(u, v) - 1 << endl;
}
return 0;
}
