#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e6;
int n, k, q, m, a[100100], p[100100], rc[100100], lev[200200], sp[20][200200], d[20][200200][2][2];
vector<int> lc[200100], v[200100];
vector<array<int, 2>> e, ld[200100], rd[200100];
void dfs(int u) {
sort(v[u].begin(), v[u].end());
int pr = e[u][0], pc = 0;
ld[u].push_back({e[u][0], 0});
for(auto x : v[u]) {
auto [pr, pc] = ld[u].back();
ld[u].push_back({e[x][1], e[x][0]-pr+1 + pc});
lev[x] = lev[u]+1, sp[0][x] = u;
dfs(x);
}
rd[u].push_back({e[u][1], 0});
for(int i=v[u].size()-1;i>=0;i--) {
int x = v[u][i];
auto [pl, pc] = rd[u].back();
rd[u].push_back({e[x][0], pl-e[x][1]+1 + pc});
}
reverse(rd[u].begin(), rd[u].end());
}
int lca(int x, int y) {
if(lev[x] < lev[y]) swap(x, y);
for(int i=19;i>=0;i--) if((1 << i) & (lev[x]-lev[y])) x = sp[i][x];
if(x == y) return x;
for(int i=19;i>=0;i--) if(sp[i][x] != sp[i][y]) x = sp[i][x], y = sp[i][y];
return sp[0][x];
}
int find_left(int u, int x) {
auto it = *prev(upper_bound(ld[u].begin(), ld[u].end(), array<int, 2>({x, INF*10})));
return it[1] + (x-it[0]);
}
int find_right(int u, int x) {
auto it = *lower_bound(rd[u].begin(), rd[u].end(), array<int, 2>({x, 0}));
return it[1] + (it[0]-x);
}
array<array<int, 4>, 2> lift(int h, int u, int x) {
auto [l, r] = e[x];
if(h < 0) {
array<int, 4> re = {u, 0, find_left(x, u), find_right(x, u)};
return {re, re};
}
int lc = u-l, rc = r-u;
lc = min(lc, rc+1), rc = min(lc+1, rc);
for(int i=19;i>=0;i--) if((1 << i) & h) {
int L = min(lc + d[i][x][0][0], rc + d[i][x][1][0]), R = min(lc + d[i][x][0][1], rc + d[i][x][1][1]);
lc = min(L, R+1), rc = min(L+1, R), x = sp[i][x];
}
auto LL = find_left(sp[0][x], e[x][1]);
auto RR = find_right(sp[0][x], e[x][0]);
return {array<int, 4>({e[x][0], lc, LL-1, RR}), {e[x][1], rc, LL, RR-1}};
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k >> q;
for(int i=1;i<=n;i++) cin >> a[i];
vector<int> s;
for(int i=1;i<=n;i++) {
while(!s.empty() && a[s.back()] <= a[i]) {
e.push_back({s.back(), i}), s.pop_back();
}
s.push_back(i);
}
s.clear();
for(int i=n;i>=1;i--) {
while(!s.empty() && a[s.back()] <= a[i]) {
e.push_back({i, s.back()}), s.pop_back();
}
s.push_back(i);
}
s.clear();
e.push_back({-INF*2, INF*2});
sort(e.begin(), e.end(), [&](auto &a, auto &b){ return tie(a[0], b[1]) < tie(b[0], a[1]); });
e.erase(unique(e.begin(), e.end()), e.end());
m = (int)e.size()-1;
for(int i=1;i<=m;i++) {
auto [l, r] = e[i];
lc[l].push_back(i), rc[r]++;
}
s.push_back(0);
for(int i=1;i<=n;i++) {
for(int j=1;j<=rc[i];j++) {
int u = s.back(); s.pop_back();
v[s.back()].push_back(u);
}
for(auto x : lc[i]) s.push_back(x);
p[i] = s.back();
}
dfs(0);
for(int i=0;i<20;i++) for(int j=1;j<=m;j++) for(int a=0;a<2;a++) for(int b=0;b<2;b++) d[i][j][a][b] = INF;
for(int i=1;i<=m;i++) {
auto [l, r] = e[i];
auto [L, R] = e[sp[0][i]];
d[0][i][0][0] = find_left(sp[0][i], l);
d[0][i][0][1] = find_right(sp[0][i], r)+1;
d[0][i][1][0] = find_left(sp[0][i], l)+1;
d[0][i][1][1] = find_right(sp[0][i], r);
}
for(int i=1;i<20;i++) for(int j=1;j<=m;j++) {
sp[i][j] = sp[i-1][sp[i-1][j]];
for(int a=0;a<2;a++) for(int b=0;b<2;b++) for(int c=0;c<2;c++) {
d[i][j][a][c] = min(d[i][j][a][c], d[i-1][j][a][b] + d[i-1][sp[i-1][j]][b][c]);
}
for(int a=0;a<2;a++) for(int b=0;b<2;b++) d[i][j][a][b] = min(d[i][j][a][b], d[i][j][a][1-b]+1);
}
while(q--) {
int S, E; cin >> S >> E;
if(S > E) swap(S, E);
int ans = INF;
for(int i=max(1, S-1);i<=S;i++) for(int j=E-1;j<=E;j++) {
int P = lca(p[i], p[j]);
auto L = lift(lev[p[i]]-lev[P]-1, S, p[i]);
auto R = lift(lev[p[j]]-lev[P]-1, E, p[j]);
// for(int i=0;i<2;i++) cout << L[i][0] << " " << L[i][1] << " " << L[i][2] << " " << L[i][3] << "\n";
// for(int i=0;i<2;i++) cout << R[i][0] << " " << R[i][1] << " " << R[i][2] << " " << R[i][3] << "\n";
for(int i=0;i<2;i++) for(int j=0;j<2;j++) {
ans = min(ans, L[i][1]+R[j][1] + min(R[j][2]-L[i][2], R[j][3]+L[i][2]+1));
}
}
cout << ans-1 << "\n";
}
}
