#include <bits/stdc++.h> #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } using namespace std; const int N = 1e5 + 5, LG = 17; int n, k, q; int a[N]; int dep[N]; int nl[N][LG], nr[N][LG]; int st[N]; int main() { ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0); // file("A") else file("task"); cin >> n >> k >> q; for(int i = 1; i <= n; ++i) cin >> a[i]; a[0] = a[n + 1] = 1e9; for(int i = 1; i <= n; ++i) { while(st[0] && a[st[st[0]]] < a[i]) --st[0]; if(st[0]) nl[i][0] = st[st[0]]; else nl[i][0] = 1; st[++st[0]] = i; } for(int i = n; i >= 1; --i) { while(st[0] && a[st[st[0]]] < a[i]) --st[0]; if(st[0]) nr[i][0] = st[st[0]]; else nr[i][0] = n; st[++st[0]] = i; } for(int j = 1; j < LG; ++j) { for(int i = 1; i <= n; ++i) { nl[i][j] = min(nl[nl[i][j - 1]][j - 1], nl[nr[i][j - 1]][j - 1]); nr[i][j] = max(nr[nr[i][j - 1]][j - 1], nr[nl[i][j - 1]][j - 1]); } } for(int _ = 1; _ <= q; ++_) { int a, b; cin >> a >> b; if(a > b) swap(a, b); int l = a, r = a, ans = 0, c; for(int i = LG - 1; i >= 0; --i) { if(max(nr[l][i], nr[r][i]) < b) { tie(l, r) = make_pair(min(nl[l][i], nl[r][i]), max(nr[l][i], nr[r][i])); ans += (1 << i); } } c = r; l = b, r = b; for(int i = LG - 1; i >= 0; --i) { if(min(nl[l][i], nl[r][i]) > c) { tie(l, r) = make_pair(min(nl[l][i], nl[r][i]), max(nr[l][i], nr[r][i])); ans += (1 << i); } } cout << ans << '\n'; } return 0; }