#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef long long ll;
//~ #define int ll
const int N = 2e5 + 5;
const int K = 20;
vector<int> edges[N];
int a[N], L[N], R[N], pos[N][K];
ar<int, 2> l[N][K], r[N][K];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, k, q; cin >> n >> k >> q;
vector<int> ss;
memset(L, -1, sizeof L);
memset(R, -1, sizeof R);
for(int i=0;i<n;i++){
cin >> a[i]; a[i]--;
while(!ss.empty() && a[ss.back()] < a[i]){
ss.pop_back();
}
if(!ss.empty()){
L[i] = ss.back();
}
ss.push_back(i);
}
ss.clear();
for(int i=n-1;~i;i--){
while(!ss.empty() && a[ss.back()] < a[i]){
ss.pop_back();
}
if(!ss.empty()){
R[i] = ss.back();
}
ss.push_back(i);
}
memset(l, 63, sizeof l);
memset(r, 63, sizeof r);
for(int i=0;i<n;i++){
l[i][0] = r[i][0] = {i, 0};
pos[i][0] = i;
}
for(int j=1;j<k;j++){
for(int i=0;i<n;i++){
auto [p, c] = l[i][j-1];
if(a[p] >= j) l[i][j] = {p, c};
else if(i != p) l[i][j] = {l[p][j][0], l[p][j][1] + c};
else if(~L[i]){
l[i][j] = l[L[i]][j]; l[i][j][1]++;
} else assert(false);
}
for(int i=n-1;~i;i--){
auto [p, c] = r[i][j-1];
if(a[p] >= j) r[i][j] = {p, c};
else if(i != p) r[i][j] = {r[p][j][0], r[p][j][1] + c};
else if(~R[i]){
r[i][j] = r[R[i]][j]; r[i][j][1]++;
} else assert(false);
}
for(int i=0;i<n;i++){
l[i][j][1] = min(l[i][j][1], l[r[i][j-1][0]][j][1] + r[i][j-1][1] + (a[r[i][j-1][0]] >= j));
r[i][j][1] = min(r[i][j][1], r[l[i][j-1][0]][j][1] + l[i][j-1][1] + (a[l[i][j-1][0]] >= j));
}
int last = 0;
for(int i=0;i<n;i++){
if(a[i] >= j) pos[i][j] = last++;
}
}
//~ for(int j=0;j<k;j++){
//~ for(int i=0;i<n;i++){
//~ cout<<l[i][j][0]<<" ";
//~ } cout<<"\n";
//~ } cout<<"\n";
//~ for(int j=0;j<k;j++){
//~ for(int i=0;i<n;i++){
//~ cout<<l[i][j][1]<<" ";
//~ } cout<<"\n";
//~ } cout<<"\n";
//~ for(int j=0;j<k;j++){
//~ for(int i=0;i<n;i++){
//~ cout<<r[i][j][0]<<" ";
//~ } cout<<"\n";
//~ } cout<<"\n";
//~ for(int j=0;j<k;j++){
//~ for(int i=0;i<n;i++){
//~ cout<<r[i][j][1]<<" ";
//~ } cout<<"\n";
//~ } cout<<"\n";
auto check = [&](int j, ar<int, 2> a, ar<int, 2> b){
if(a[0] > n || b[0] > n) assert(false);
//~ cout<<j<<" "<<a[0]<<" "<<b[0]<<" "<<abs(pos[a[0]][j] - pos[b[0]][j])<<" "<<a[1] + b[1]<<"\n";
return abs(pos[a[0]][j] - pos[b[0]][j]) + a[1] + b[1];
};
while(q--){
int a, b; cin >> a >> b;
a--, b--;
int res = 1e9;
for(int j=0;j<k;j++){
res = min(res, check(j, l[a][j], l[b][j]));
res = min(res, check(j, l[a][j], r[b][j]));
res = min(res, check(j, r[a][j], l[b][j]));
res = min(res, check(j, r[a][j], r[b][j]));
}
cout<<--res<<"\n";
}
}
/*
15 5 1
5
4
1
2
3
1
1
2
4
5
4
1
5
3
5
8 1
*/
