#include <bits/stdc++.h>
using namespace std;
using nagai = long long;
#define sz(x) int((x).size())
const int LG=17;
const int N=1<<LG;
const int oo=0x3f3f3f3f;
int n,k,q;
int l[N];
int go[LG][N][2];
int cost[LG][N][2];
vector<int>occ[N];
int count_occ(int lev,int l,int r){
return lower_bound(occ[lev].begin(),occ[lev].end(),r)-lower_bound(occ[lev].begin(),occ[lev].end(),l);
}
pair<int,int> mx[2*N];
void build(){
for(int i=0;i<n;++i)
mx[N+i]={l[i],i};
for(int i=n;i<N;++i)
mx[N+i]={0,0};
for(int i=N-1;i>=0;--i)
mx[i]=max(mx[2*i],mx[2*i+1]);
}
int ft(int x,int l,int r,int ql,int qx){
if(r<=ql||mx[x].first<qx)
return -1;
if(r-l==1)
return mx[x].second;
int m=(l+r)/2;
int ans=ft(x*2,l,m,ql,qx);
if(ans==-1)ans=ft(x*2+1,m,r,ql,qx);
return ans;
}
int lst(int x,int l,int r,int qr,int qx){
if(l>=qr||mx[x].first<qx)
return -1;
if(r-l==1)
return mx[x].second;
int m=(l+r)/2;
int ans=lst(x*2+1,m,r,qr,qx);
if(ans==-1)ans=lst(x*2,l,m,qr,qx);
return ans;
}
pair<int,int> getmax(int l,int r){
l+=N;
r+=N;
pair<int,int> ans={-1,-1};
while(l<r){
if(l&1)
ans=max(ans,mx[l++]);
if(r&1)
ans=max(ans,mx[--r]);
l/=2,r/=2;
}
return ans;
}
int pref[N],suff[N];
int cntcalled=0;
pair<int,int> goleri(int x,int lev,int dir,int from,int mx=oo){
if(mx<0)return {x,0};
++cntcalled;
if(l[x]>=lev)return {x,0};
if(l[go[0][x][dir]]>=lev)
return {go[0][x][dir],cost[0][x][dir]};
if(dir==0&&l[pref[x]]<lev)
return {pref[x],oo};
if(dir==1&&l[suff[x]]<lev)
return {suff[x],oo};
for(int i=from;i>=0;--i){
if(l[x]+(1<<i)<=lev){
auto p=goleri(go[i][x][dir],lev,dir,i-1,mx-cost[i][x][dir]);
p.second+=cost[i][x][dir];
if(l[go[i][x][dir]]>=lev)
return p;
// auto q=make_pair(go[i][x][1^dir],cost[i][x][1^dir]+1);
auto q=goleri(go[i][x][1^dir],lev,dir,i-1,min(mx,p.second)-cost[i][x][1^dir]);
q.second+=cost[i][x][1^dir];
if(dir==0&&q.first>x||dir==1&&q.first<x)
++q.second,q.first=p.first;
return {p.first,min(q.second,p.second)};
}
}
return {x,oo};
exit(239);
}
inline pair<int,int> gole(int x,int lev,int from=LG-1){
return goleri(x,lev,0,from);
}
inline pair<int,int> gori(int x,int lev,int from=LG-1){
return goleri(x,lev,1,from);
}
int d[N];
int stup_calc(int a,int b){
if(b<a)
swap(a,b);
int ans=0;
for(int i=a;i<=b;++i){
if(l[i]>=l[a]||l[i]>=l[b])
++ans;
}
return ans-1;
}
struct cmp{
bool operator()(int a,int b) const{
if(d[a]!=d[b])
return d[a]<d[b];
return a<b;
};
};
int stupid(int a,int b){
memset(d,0x3f,sizeof d);
d[a]=0;
set<int,cmp>st;
st.insert(a);
while(st.size()){
int x=*st.begin();
st.erase(st.begin());
if(x==b)
return d[x];
for(int y=0;y<n;++y){
int v=stup_calc(x,y);
if(d[x]+v<d[y]){
st.erase(y);
d[y]=d[x]+v;
st.insert(y);
}
}
}
assert(false);
}
bool st=false;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
n=100000,k=-1,q=100000;
cin>>n>>k>>q;
for(int i=0;i<n;++i){
cin>>l[i];
--l[i];
occ[l[i]].push_back(i);
}
memset(cost,0,sizeof cost);
memset(go,0,sizeof go);
build();
pref[0]=0;
for(int i=1;i<n;++i)
if(l[i]>=l[pref[i-1]])pref[i]=i;
else pref[i]=pref[i-1];
suff[n-1]=n-1;
for(int i=n-2;i>=0;--i)
if(l[i]>=l[suff[i+1]])suff[i]=i;
else suff[i]=suff[i+1];
for(int i=0;i<n;++i){
if((go[0][i][0]=lst(1,0,N,i,l[i]+1))==-1)
go[0][i][0]=i;
else
cost[0][i][0]=count_occ(l[i],go[0][i][0],i+1);
if((go[0][i][1]=ft(1,0,N,i,l[i]+1))==-1)
go[0][i][1]=i;
else
cost[0][i][1]=count_occ(l[i],i,go[0][i][1]);
if(go[0][i][1]!=i&&go[0][i][0]!=i){
cost[0][i][0]=min(cost[0][i][0],cost[0][i][1]+1);
cost[0][i][1]=min(cost[0][i][1],cost[0][i][0]+1);
}
}
// cerr<<gole(1,6,1).first<<'\n';
for(int i=1;i<LG;++i){
for(int j=0;j<n;++j){
go[i][j][0]=go[i][j][1]=j;
int lev=l[j]+(1<<i);
if(l[j]+(1<<i-1)>=l[pref[j]])
go[i][j][0]=go[i-1][j][0],cost[i][j][0]=cost[i-1][j][0];
else{
auto p=gole(j,min(lev,l[pref[j]]),i-1);
go[i][j][0]=p.first,cost[i][j][0]=p.second;
}
if(l[j]+(1<<i-1)>=l[suff[j]])
go[i][j][1]=go[i-1][j][1],cost[i][j][1]=cost[i-1][j][1];
else{
auto q=gori(j,min(lev,l[suff[j]]),i-1);
go[i][j][1]=q.first,cost[i][j][1]=q.second;
}
}
}
for(int i=0;i<q;++i){
int a,b;
cin>>a>>b;
--a,--b;
if(a>b)swap(a,b);
int ans=b-a;
int kek=getmax(a,b+1).first;
vector<pair<int,int>>as={gori(a,kek)};
vector<pair<int,int>>bs={gole(b,kek)};
for(auto a1:as)
for(auto b1:bs){
if(l[a1.first]>=kek&&l[b1.first]>=kek){
if(a1.first==b1.first)
ans=min(ans,a1.second+b1.second);
ans=min(ans,a1.second+b1.second+count_occ(kek,a1.first+1,b1.first)+1);
}
}
auto a1=gole(a,kek+1);
auto b1=gori(b,kek+1);
if(l[a1.first]>kek&&l[b1.first]>kek)
ans=min(ans,a1.second+b1.second+1);
cout<<ans-1<<'\n';
}
return 0;
}
