#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> ii; #define fi first #define se second #define all(x) x.begin(), x.end() #define sz(x) (int)(x.size()) #define MASK(i) (1ll << i) #define debug cout << "[Debug line] " << __LINE__ << ": " const int N = 2e5 + 5; const int M = 2e3 + 5; const int INF = INT_MAX; int n, k, q; ii qry[N]; int a[N]; vector<int> g[N]; namespace sub12 { bool check() { return ((n <= 100 && q <= 50 && k <= 100) || q <= 50); } int d[N], prv[N], nxt[N]; bool vis[N]; void bfs(int s) { for (int i = 1; i <= n; i++) { vis[i] = false, d[i] = INF; } d[s] = 0; vis[s] = true; queue<int> qe; qe.push(s); while (!qe.empty()) { int u = qe.front(); qe.pop(); for (int v : g[u]) { if (!vis[v]) { d[v] = d[u] + 1; vis[v] = true; qe.push(v); } } } } void solve() { stack<int> st; for (int i = 1; i <= n; i++) { while (!st.empty() && a[st.top()] < a[i]) st.pop(); prv[i] = (st.empty()) ? -1 : st.top(); st.push(i); } while (sz(st)) st.pop(); for (int i = n; i >= 1; i--) { while (!st.empty() && a[st.top()] < a[i]) st.pop(); nxt[i] = (st.empty() ? -1 : st.top()); st.push(i); } for (int i = 1; i <= n; i++) { int l = prv[i], r = nxt[i]; if (l != -1) { g[i].push_back(l); if (a[l] > a[i]) g[l].push_back(i); } if (r != -1) { g[i].push_back(r); if (a[r] > a[i]) g[r].push_back(i); } } for (int i = 1; i <= q; i++) { int u = qry[i].fi, v = qry[i].se; bfs(u); cout << d[v] - 1 << '\n'; } } } void solve() { cin >> n >> k >> q; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= q; i++) { int u, v; cin >> u >> v; qry[i] = {u, v}; } sub12::solve(); return; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // #define TASK "PERMATRIX" // freopen(TASK".inp", "r", stdin); // freopen(TASK".out", "w", stdout); int T = 1; // cin >> T; while (T--) { solve(); } }