#include <bits/stdc++.h> using namespace std; #define f first #define s second #define pb(x) push_back(x) #define sz(x) (int) x.size() #define all(x) x.begin(), x.end() #define un(x) (x).erase(unique(all(x)), x.end()) typedef long long ll; typedef double db; typedef pair <int, int> ii; typedef pair <ll, ll> pll; typedef vector <ll> V; const int N = 2e5 + 10; // template <class T1, class Gz> void add(T1 &x, Gz y) { x += y; if (x < 0) x += mod; if (x >= mod) x -= mod; } template <class T1, class Gz> bool maximize(T1 &x, Gz y) { if (x < y) { x = y; return true; } return false; } template <class T1, class Gz> bool minimize(T1 &x, Gz y) { if (x > y) { x = y; return true; } return false; } int n, k, q; int a[N]; int L[N], R[N]; int joinL[20][N], joinR[20][N]; vector <int> ed[N]; 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 >> a[i]; } stack <int> st; for(int u = 1; u <= n; u++) { while (sz(st) && a[st.top()] < a[u]) st.pop(); L[u] = sz(st) ? st.top() : u; st.push(u); } while (sz(st)) st.pop(); for(int u = n; u >= 1; u--) { while (sz(st) && a[st.top()] < a[u]) st.pop(); R[u] = sz(st) ? st.top() : u; st.push(u); } for(int i = 1; i <= n; i++) { joinL[0][i] = L[i]; joinR[0][i] = R[i]; } for(int j = 1; j < 20; j++) { for(int i = 1; i <= n; i++) { int l = joinL[j - 1][i], r = joinR[j - 1][i]; joinL[j][i] = min(joinL[j - 1][l], joinL[j - 1][r]); joinR[j][i] = max(joinR[j - 1][l], joinR[j - 1][r]); } } for(int i = 1; i <= q; i++) { int u, v; cin >> u >> v; if (u > v) swap(u, v); int l, r; l = r = u; int ans = 0; for(int j = 19; j >= 0; j--) { if (max(joinR[j][l], joinR[j][r]) < v) { ans += 1 << j; int p = l, q = r; l = min(joinL[j][p], joinL[j][q]); r = max(joinR[j][p], joinR[j][q]); } } u = r; l = r = v; for(int j = 19; j >= 0; j--) { if (min(joinL[j][l], joinL[j][r]) > u) { ans += 1 << j; int p = l, q = r; l = min(joinL[j][p], joinL[j][q]); r = max(joinR[j][p], joinR[j][q]); } } cout << ans << endl; } return 0; }