#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)
int n,k,q;
int arr[100023];
int optl[100023][17],optr[100023][17];
int cal1(int a,int b){
int res=0;
int l=a,r=a;
for(int i=17-1;i>=0;i--){
if(optr[l][i]>b||optr[r][i]>b)continue;
res+=(1<<i);
int l2=min(optl[l][i],optl[r][i]);
int r2=max(optr[l][i],optr[r][i]);
l=l2;r=r2;
}
a=r;
if(a==b)return res-1;
l=b;r=b;
for(int i=17-1;i>=0;i--){
if(optl[l][i]<=a||optl[r][i]<=a)continue;
res+=(1<<i);
int l2=min(optl[l][i],optl[r][i]);
int r2=max(optr[l][i],optr[r][i]);
l=l2;r=r2;
}
return res;
}
int cal2(int a,int b){
int res=0;
int l=b,r=b;
for(int i=17-1;i>=0;i--){
if(optl[l][i]<a||optl[r][i]<a)continue;
res+=(1<<i);
int l2=min(optl[l][i],optl[r][i]);
int r2=max(optr[l][i],optr[r][i]);
l=l2;r=r2;
}
b=r;
if(a==b)return res-1;
l=a;r=a;
for(int i=17-1;i>=0;i--){
if(optr[l][i]>=b||optr[r][i]>=b)continue;
res+=(1<<i);
int l2=min(optl[l][i],optl[r][i]);
int r2=max(optr[l][i],optr[r][i]);
l=l2;r=r2;
}
return res;
}
int cal3(int a,int b){
int res=0;
int l=a,r=a;
for(int i=17-1;i>=0;i--){
if(optr[l][i]>b||optr[r][i]>b)continue;
res+=(1<<i);
int l2=min(optl[l][i],optl[r][i]);
int r2=max(optr[l][i],optr[r][i]);
l=l2;r=r2;
}
a=max(optr[l][0],optr[r][0]);
res++;
if(a==b)return res-1;
l=b;r=b;
for(int i=17-1;i>=0;i--){
if(optr[l][i]>=a||optr[r][i]>=a)continue;
res+=(1<<i);
int l2=min(optl[l][i],optl[r][i]);
int r2=max(optr[l][i],optr[r][i]);
l=l2;r=r2;
}
return res;
}
int cal4(int a,int b){
int res=0;
int l=b,r=b;
for(int i=17-1;i>=0;i--){
if(optl[l][i]<a||optl[r][i]<a)continue;
res+=(1<<i);
int l2=min(optl[l][i],optl[r][i]);
int r2=max(optr[l][i],optr[r][i]);
l=l2;r=r2;
}
b=min(optl[l][0],optl[r][0]);
res++;
if(a==b)return res-1;
l=a;r=a;
for(int i=17-1;i>=0;i--){
if(optl[l][i]<=b||optl[r][i]<=b)continue;
res+=(1<<i);
int l2=min(optl[l][i],optl[r][i]);
int r2=max(optr[l][i],optr[r][i]);
l=l2;r=r2;
}
return res;
}
int cal(int a,int b){
if(a>b)swap(a,b);
return min(min(cal1(a,b),cal2(a,b)),min(cal3(a,b),cal4(a,b)));
}
signed main(){
ios_base::sync_with_stdio(23^23);cin.tie(0);
cin>>n>>k>>q;
for(int i=1;i<=n;i++){
cin>>arr[i];
}
vector<int>sta={1};
optl[1][0]=0;
optl[0][0]=0;
optr[0][0]=0;
for(int i=2;i<=n;i++){
while(arr[sta.back()]<arr[i])sta.pop_back();
optl[i][0]=sta.back();
sta.pb(i);
}
sta.clear();
sta={n};
optr[n][0]=n+1;
optl[n+1][0]=n+1;
optr[n+1][0]=n+1;
for(int i=n-1;i>=1;i--){
while(arr[sta.back()]<arr[i])sta.pop_back();
optr[i][0]=sta.back();
sta.pb(i);
}
sta.clear();
for(int j=1;j<17;j++){
for(int i=0;i<=n+1;i++){
optl[i][j]=min(optl[optl[i][j-1]][j-1],optl[optr[i][j-1]][j-1]);
optr[i][j]=max(optr[optr[i][j-1]][j-1],optr[optl[i][j-1]][j-1]);
}
}
while(q--){
int a,b;cin>>a>>b;
cout<<cal(a,b)<<endl;
}
}
