// vaziat meshki-ghermeze !
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
const ll Mod = 1000000007LL;
const int N = 1e5 + 10;
const int Inf = N + N;
const ll Log = 30;
int n, k, q;
int a[N], sz[N];
int L[N], wL[N], l[N], szl[N];
int R[N], wR[N], r[N], szr[N];
typedef pair<int, int> pii;
typedef pair<int, int> T;
typedef pair<int, T> P;
P nxt(T A){
pii lf = {wL[A.F], -a[L[A.F]]};
pii rt = {wR[A.S], -a[R[A.S]]};
if(lf == rt)
return {lf.F, {L[A.F], R[A.S]} };
if(lf < rt)
return {lf.F, {L[A.F], L[A.F]} };
return {rt.F, {R[A.S], R[A.S]}};
}
int Edge(int u, int v){
if(u > v) swap(u, v);
int res = Inf;
if(R[u] > v)
res = min(res, szl[v] - szl[u]);
if(L[v] < u)
res = min(res, szr[u] - szr[v]);
if(res < 0){
debug(res);
cerr << "!! " << u << ' ' << v << '\n';
cerr << "## " << szl[u] << ' ' << szl[v] << '\n';
assert(false);
}
return res;
}
const int FN = 11;
int dp[FN][FN];
int Floyd(vector<int> V, vector<int> S, vector<int> T){
int res = Inf;
int _n = V.size();
memset(dp, 31, sizeof dp);
for(int i = 0; i < _n; i++)
for(int j = 0; j < _n; j++)
dp[i][j] = dp[j][i] = Edge(V[i], V[j]);
for(int k = 0; k < _n; k++)
for(int i = 0; i < _n; i++)
for(int j = 0; j < _n; j++)
dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k][j]);
for(auto sr : S)
for(auto ds : T)
res = min(res, dp[sr][ds]);
return res;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> k >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
a[0] = a[n + 1] = k + 1;
{ // stack
vector<int> V = {0};
for(int i = 1; i <= n; i++){
while(a[V.back()] < a[i]) V.pop_back();
l[i] = V.back();
V.pb(i);
sz[i] = V.size();
}
V = {0};
for(int i = 1; i <= n; i++){
while(a[V.back()] <= a[i]) V.pop_back();
L[i] = V.back();
V.pb(i);
}
sz[0] = 1; wL[0] = n; l[0] = L[0] = 0;
for(int i = 1; i <= n; i++)
wL[i] = L[i] != 0 ? sz[i] - sz[L[i]] : Inf;
memcpy(szl, sz, sizeof sz);
V = {n + 1};
for(int i = n; i >= 1; i--){
while(a[V.back()] < a[i]) V.pop_back();
r[i] = V.back();
V.pb(i);
sz[i] = V.size();
}
V = {n + 1};
for(int i = n; i >= 1; i--){
while(a[V.back()] <= a[i]) V.pop_back();
R[i] = V.back();
V.pb(i);
}
sz[n + 1] = 1; wR[n + 1] = n; r[n + 1] = R[n + 1] = n + 1;
for(int i = 1; i <= n; i++)
wR[i] = R[i] != n + 1 ? sz[i] - sz[R[i]] : Inf;
memcpy(szr, sz, sizeof sz);
}
// auto res = nxt({3, 3});
// cerr << res.F << ' ' << res.S.F << ' ' << res.S.S << '\n';
// debug(Edge(5, 1));
// debug(R[1]);
// exit(0);
int src, des;
for(int i = 0; i < q; i++){
cin >> src >> des;
if(src > des) swap(src, des);
int idx = max_element(a + src, a + des + 1) - a;
int mx = a[idx];
int lx = src, rx = des;
for(int j = src; j <= des; j++) if(a[j] == mx) rx = j;
for(int j = src; j <= des; j++) if(a[j] == mx){ lx = j; break; }
pii s1 = {src, src};
int res = 0;
while(a[s1.F] < mx){
auto del = nxt(s1);
if(a[del.S.F] >= mx) break;
res += del.F;
s1 = del.S;
}
// cerr << "!! " << s1.F << ' ' << s1.S << ' ' << res << '\n';
pii s2 = {des, des};
while(a[s2.F] < mx){
auto del = nxt(s2);
if(a[del.S.F] >= mx) break;
res += del.F;
s2 = del.S;
}
// cerr << "$$ " << s2.F << ' ' << s2.S << ' ' << res << '\n';
// debug(Edge(5, 1));
// debug(Edge(1, 9));
vector<int> nodes = {lx, rx, s1.F, s1.S, s2.F, s2.S};
vector<int> S = {2, 3};
vector<int> T = {4, 5};
if(L[lx] != 0) nodes.pb(L[lx]);
if(R[rx] != n + 1) nodes.pb(R[rx]);
if(l[lx] != 0) nodes.pb(l[lx]);
if(r[rx] != n + 1) nodes.pb(r[rx]);
cout << res -1 + Floyd(nodes, S, T) << '\n';
}
return 0;
}
/*
9 3 3
3 1 1 1 2 2 2 3 3
2 4
4 9
6 7
*/
