#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; pii jump[100001][17]; int arr[100001]; int max_[100001][17]; int same_ind[100001]; int query(int l, int r) { int lg = __lg(r-l+1); return max(max_[l][lg],max_[r-(1<<lg)+1][lg]); } pii do_jump(pii x, int bit) { return {min(jump[x.ff][bit].ff,jump[x.ss][bit].ff),max(jump[x.ff][bit].ss,jump[x.ss][bit].ss)}; } pair<int,pii> jump_to_level(pii x, int l) { int ans = 0; for(int bit = 16; bit >= 0; bit--) { pii new_x = do_jump(x,bit); if(max(arr[new_x.ff],arr[new_x.ss]) < l) { ans += (1<<bit); x = new_x; } } if(max(arr[x.ff],arr[x.ss]) < l) { x = do_jump(x,0); ans++; } return {ans,x}; } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random_start(); int n,k,q; cin >> n >> k >> q; rep2(i,1,n) cin >> arr[i]; map<int,int> cur_ind; rep2(i,1,n) same_ind[i] = cur_ind[arr[i]]++; rep2(i,1,n) max_[i][0] = arr[i]; rep2(bit,1,16) rep2(i,1,n) max_[i][bit] = max(max_[i][bit-1],(i+(1<<(bit-1)) <= n ? max_[i+(1<<(bit-1))][bit-1] : -1)); stack<int> st; rep2(i,1,n) { while(siz(st) > 0 && arr[st.top()] < arr[i]) st.pop(); if(siz(st) == 0) jump[i][0].ff = i; else jump[i][0].ff = st.top(); st.push(i); } st = {}; for(int i = n; i >= 1; i--) { while(siz(st) > 0 && arr[st.top()] < arr[i]) st.pop(); if(siz(st) == 0) jump[i][0].ss = i; else jump[i][0].ss = st.top(); st.push(i); } rep2(bit,1,16) { rep2(i,1,n) { jump[i][bit] = do_jump(jump[i][bit-1],bit-1); } } vi v1; vi v2; rep(qq,q) { int a2,b2; cin >> a2 >> b2; if(a2 > b2) swap(a2,b2); pii a = {a2,a2}; pii b = {b2,b2}; int mx = query(a2,b2); int ans = 1e9; pair<int,pii> p1 = jump_to_level(a,mx); pair<int,pii> p2 = jump_to_level(b,mx); a = p1.ss; b = p2.ss; int max_a = -1; if(arr[a.ff] == mx) max_a = same_ind[a.ff]; if(arr[a.ss] == mx) max_a = same_ind[a.ss]; int min_b = 1e9; if(arr[b.ss] == mx) min_b = same_ind[b.ss]; if(arr[b.ff] == mx) min_b = same_ind[b.ff]; ans = min(ans,p1.ff+p2.ff+min_b-max_a); a = {a2,a2}; b = {b2,b2}; p1 = jump_to_level(a,mx+1); p2 = jump_to_level(b,mx+1); a = p1.ss; b = p2.ss; v1 = {}; v2 = {}; if(arr[a.ff] > mx) v1.pb(a.ff); if(arr[a.ss] > mx) v1.pb(a.ss); if(arr[b.ff] > mx) v2.pb(b.ff); if(arr[b.ss] > mx) v2.pb(b.ss); if(siz(v1) > 0 && siz(v2) > 0) { int is = 1; forall(it,v1) forall(it2,v2) if(it == it2) is = 0; ans = min(ans,p1.ff+p2.ff+is); } cout << ans-1 << "\n"; } }