#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define pb push_back
#define sz(a) (ll)a.size()
#define all(x) (x).begin(), (x).end()
int main() {
ll n, k, q; cin >> n >> k >> q;
vector<ll> lvl(n); for(auto& u : lvl) cin >> u;
vector<vector<vector<ll>>> stp(2, vector<vector<ll>>(n, vector<ll>(18, 0LL))); //v[left/right][place][2^?]=first point place will reach
stack<ll> st;
for(ll i=0; i<n; i++){
while(!st.empty() && lvl[st.top()]<lvl[i]) st.pop();
if(st.empty()) stp[0][i][0]=i;
else stp[0][i][0]=st.top();
st.push(i);
}
while(!st.empty()) st.pop();
for(ll i=n-1; i>=0; i--){
while(!st.empty() && lvl[st.top()]<lvl[i]) st.pop();
if(st.empty()) stp[1][i][0]=i;
else stp[1][i][0]=st.top();
st.push(i);
}
for(int i=1; i<=17; i++){
for(ll j=0; j<n; j++){
stp[0][j][i]=min(stp[0][stp[0][j][i-1]][i-1], stp[0][stp[1][j][i-1]][i-1]);
stp[1][j][i]=max(stp[1][stp[0][j][i-1]][i-1], stp[1][stp[1][j][i-1]][i-1]);
}
}
while(q--){
ll ans=0;
//find the 2 sticked range
ll a, b, l, r; cin >> a >> b;
a--; b--;
if(a>b) swap(a, b);
l=r=a;
for(int i=17; i>=0; i--){
ll u=min(stp[0][l][i], stp[0][r][i]), v=max(stp[1][l][i], stp[1][r][i]);
if(v<b){
l=u, r=v;
ans+=pow(2, i);
}
}
a=r;
l=r=b;
for(int i=17; i>=0; i--){
ll u=min(stp[0][l][i], stp[0][r][i]), v=max(stp[1][l][i], stp[1][r][i]);
if(a<u){
l=u, r=v;
ans+=pow(2, i);
}
}
//no need +1
cout << ans << endl;
}
}
