#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define fi first
#define se second
const int MX = 1e5 + 10;
const int LG = 18;
const int INF = 1e9 + 7;
int N, K, Q, arr[MX], lf[MX], rg[MX], L[MX][LG], R[MX][LG];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> K >> Q;
for(int i = 1; i <= N; i++) cin >> arr[i];
{
vector<int> stk;
for(int i = 1; i <= N; i++){
for(; !stk.empty() && arr[stk.back()] < arr[i]; ) stk.pop_back();
if(!stk.empty()) lf[i] = stk.back();
else lf[i] = 0;
stk.push_back(i);
}
stk.clear();
}
{
vector<int> stk;
for(int i = N; i >= 1; i--){
for(; !stk.empty() && arr[stk.back()] < arr[i]; ) stk.pop_back();
if(!stk.empty()) rg[i] = stk.back();
else rg[i] = MX - 1;
stk.push_back(i);
}
}
for(int j = 0; j < LG; j++){
R[0][j] = L[0][j] = 0; L[MX - 1][j] = R[MX - 1][j] = MX - 1;
if(j == 0){
for(int i = 1; i <= N; i++) L[i][j] = lf[i], R[i][j] = rg[i];
}else{
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 q = 0; q < Q; q++){
int a, b; cin >> a >> b;
if(a > b) swap(a, b);
int la = a, ra = a, ans = 0;
for(int j = LG - 1; j >= 0; j--){
if(max(R[ra][j], R[la][j]) <= b){
ans += 1 << j;
int temp_la = la, temp_ra = ra;
la = min(L[temp_la][j], L[temp_ra][j]), ra = max(R[temp_la][j], R[temp_ra][j]);
}
}
int lb = b, rb = b;
for(int j = LG - 1; j >= 0; j--){
if(min(L[lb][j], L[rb][j]) >= ra){
ans += 1 << j;
int tl = lb, tr = rb;
lb = min(L[tl][j], L[tr][j]), rb = max(R[tl][j], R[tr][j]);
}
}
if(ra == lb) ans--;
cout << ans << '\n';
}
}
