#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44
using namespace std;
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int n, k, q, i;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> k >> q;
vector <int> h(n + 1);
for(i = 1; i <= n; i++) {
cin >> h[i];
}
vector < vector <int> > l(n + 1, vector <int>(17)), r(n + 1, vector <int>(17));
vector <int> stk;
for(i = 1; i <= n; i++) {
while(stk.size() && h[stk.back()] < h[i]) {
stk.pop_back();
}
if(stk.size()) {
l[i][0] = stk.back();
}
else {
l[i][0] = 1;
}
stk.push_back(i);
}
stk.clear();
for(i = n; i >= 1; i--) {
while(stk.size() && h[stk.back()] < h[i]) {
stk.pop_back();
}
if(stk.size()) {
r[i][0] = stk.back();
}
else {
r[i][0] = n;
}
stk.push_back(i);
}
for(int bit = 1; bit <= 16; bit++) {
for(i = 1; i <= n; i++) {
l[i][bit] = min(l[l[i][bit - 1]][bit - 1], l[r[i][bit - 1]][bit - 1]);
r[i][bit] = max(r[r[i][bit - 1]][bit - 1], r[l[i][bit - 1]][bit - 1]);
if(l[i][bit] == 0) {
l[i][bit] = 1;
}
if(r[i][bit] == 0) {
r[i][bit] = n;
}
}
}
while(q--) {
int x, y;
cin >> x >> y;
if(x > y) swap(x, y);
int left = x, right = x;
int ans = 0;
for(int bit = 16; bit >= 0; bit--) {
int curl = min(l[left][bit], l[right][bit]);
int curr = max(r[left][bit], r[right][bit]);
if(curr < y) {
ans += (1 << bit);
left = curl;
right = curr;
}
}
int pos = right;
left = right = y;
for(int bit = 16; bit >= 0; bit--) {
int curl = min(l[left][bit], l[right][bit]);
int curr = max(r[left][bit], r[right][bit]);
if(curl > pos) {
ans += (1 << bit);
left = curl;
right = curr;
}
}
cout << ans << "\n";
}
//cin.close();
//cout.close();
return 0;
}
