// High above the clouds there is a rainbow...
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int maxn=1e5+10;
int a[maxn],bef[maxn],aft[maxn],n;
pair<int,pii> f(int pos,int l,int r){
int L=pos,R=pos,ans=0;
while(1){
int LL,RR;
if(a[L]<a[R]) LL=bef[R],RR=aft[R];
else if(a[L]>a[R]) RR=aft[L],LL=bef[L];
else LL=bef[L],RR=aft[R];
if(l<LL && RR<r) L=LL,R=RR,ans++;
else break;
}
return {ans,{L,R}};
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);
int k,q;cin>>n>>k>>q;
for(int i=0;i<n;i++){
cin>>a[i], --a[i];
a[i]=min(a[i],k-1);
}
for(int i=0;i<n;i++){
bef[i]=i-1;
while(bef[i]>=0 && a[bef[i]]<a[i])
bef[i]=bef[bef[i]];
}
for(int i=n-1;i>=0;i--){
aft[i]=i+1;
while(aft[i]<n && a[aft[i]]<a[i])
aft[i]=aft[aft[i]];
}
bef[0]=0, aft[n-1]=n-1;
while(q--){
int A,B; cin>>A>>B; --A,--B;
if(A>B) swap(A,B);
pair<int,pii> aa=f(A,-1,B);
pair<int,pii> bb=f(B,aa.S.S,n);
cout<<aa.F+bb.F<<"\n";
}
return 0;
}
// Deathly mistakes:
// * Read the problem curfully.
// * Check maxn.
// * Overflows.
