#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
stack < int > st;
int a[N], L[N][19], R[N][19];
main () {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int n, k, q;
cin >> n >> k >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
stack < int > st;
st.push(0);
a[0] = k + 1;
for (int i = 1; i <= n; ++i) {
while (a[st.top()] < a[i]) {
st.pop();
}
L[i][0] = st.top();
st.push(i);
}
while (st.size())
st.pop();
st.push(n + 1);
a[n + 1] = k + 1;
for (int i = n; i >= 1; --i) {
while (a[st.top()] < a[i]) {
st.pop();
}
R[i][0] = st.top();
st.push(i);
}
while (st.size())
st.pop();
for (int i = 1; i <= n; ++i) {
if (L[i][0] == 0) {
L[i][0] = i;
}
if (R[i][0] == n + 1) {
R[i][0] = i;
}
}
for (int j = 1; j <= 17; ++j) {
for (int i = 1; i <= n; ++i) {
L[i][j] = min(L[L[i][j - 1]][j - 1], L[R[i][j - 1]][j - 1]);
R[i][j] = max(R[L[i][j - 1]][j - 1], R[R[i][j - 1]][j - 1]);
}
}
for (int i = 1; i <= q; ++i) {
int a, b, lt, rt, l, r, c, ans = 0;
cin >> a >> b;
if (a > b) swap(a, b);
l = r = a;
for (int j = 17; j >= 0; --j) {
if (max(R[l][j], R[r][j]) < b) {
ans += (1 << j);
lt = l, rt = r;
l = min(L[lt][j], L[rt][j]);
r = max(R[lt][j], R[rt][j]);
}
}
c = r, l = r = b;
for (int j = 17; j >= 0; --j) {
if (c < min(L[l][j], L[r][j])) {
ans += (1 << j);
lt = l, rt = r;
l = min(L[lt][j], L[rt][j]);
r = max(R[lt][j], R[rt][j]);
}
}
cout << ans << "\n";
}
}
