#include <bits/stdc++.h>
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
const int N = 1e5 + 5, LG = 17;
int n, k, q;
int a[N];
int dep[N];
int nl[N][LG], nr[N][LG];
int st[N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
// file("A") else file("task");
cin >> n >> k >> q;
for(int i = 1; i <= n; ++i) cin >> a[i];
a[0] = a[n + 1] = 1e9;
for(int i = 1; i <= n; ++i) {
while(st[0] && a[st[st[0]]] < a[i]) --st[0];
if(st[0]) nl[i][0] = st[st[0]];
else nl[i][0] = 1;
st[++st[0]] = i;
}
for(int i = n; i >= 1; --i) {
while(st[0] && a[st[st[0]]] < a[i]) --st[0];
if(st[0]) nr[i][0] = st[st[0]];
else nr[i][0] = n;
st[++st[0]] = i;
}
for(int j = 1; j < LG; ++j) {
for(int i = 1; i <= n; ++i) {
nl[i][j] = min(nl[nl[i][j - 1]][j - 1], nl[nr[i][j - 1]][j - 1]);
nr[i][j] = max(nr[nr[i][j - 1]][j - 1], nr[nl[i][j - 1]][j - 1]);
}
}
for(int _ = 1; _ <= q; ++_) {
int a, b;
cin >> a >> b;
if(a > b) swap(a, b);
int l = a, r = a, ans = 0, c;
for(int i = LG - 1; i >= 0; --i) {
if(max(nr[l][i], nr[r][i]) < b) {
tie(l, r) = make_pair(min(nl[l][i], nl[r][i]), max(nr[l][i], nr[r][i]));
ans += (1 << i);
}
}
c = r;
l = b, r = b;
for(int i = LG - 1; i >= 0; --i) {
if(min(nl[l][i], nl[r][i]) > c) {
tie(l, r) = make_pair(min(nl[l][i], nl[r][i]), max(nr[l][i], nr[r][i]));
ans += (1 << i);
}
}
cout << ans << '\n';
}
return 0;
}
