#include<bits/stdc++.h>
#define N 100005
#define S 20 
using namespace std;
int n,k,q,a[N],nxt[N][S],lst[N][S],mxlpos[S][N],mxrpos[S][N],tp,stk[N],lg2[N];
int mxl(int u,int v){
	if(u>v)swap(u,v); 
	if(a[u]<a[v])return v; 
	return u;
}
int mxr(int u,int v){
	if(u>v)swap(u,v);
	if(a[u]<=a[v])return v; 
	return u;
}
int qryl(int l,int r){
	int kk=lg2[r-l+1];
	return mxl(mxlpos[kk][l],mxlpos[kk][r-(1<<kk)+1]);
}
int qryr(int l,int r){
	int kk=lg2[r-l+1];
	return mxr(mxrpos[kk][l],mxrpos[kk][r-(1<<kk)+1]);
}
int qlp(int l,int pos){
	int ans=0,r=l;
	if(l>pos){
		ans=114514;
	}
	if(l<pos){
		++ans;
		for(int i=S-1;i>=0;i--)
			if(max(nxt[l][i],nxt[r][i])<pos){
				int tmp=max(nxt[l][i],nxt[r][i]);
				l=min(lst[l][i],lst[r][i]),r=tmp,ans+=(1<<i);
			}
	}
	return ans;
}
int qpr(int pos,int r){
	int ans=0,l=r;
	if(r<pos){
		ans=114514;
	}
	if(r>pos){
		++ans;
		for(int i=S-1;i>=0;i--)
			if(min(lst[l][i],lst[r][i])>pos){
				int tmp=min(lst[l][i],lst[r][i]);
				r=max(nxt[l][i],nxt[r][i]),l=tmp,ans+=(1<<i);
			}
	}
	return ans;
}
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>k>>q;
	for(int i=1;i<=n;i++)cin>>a[i],mxlpos[0][i]=mxrpos[0][i]=i;
	for(int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;
	for(int i=1;i<=n;i++){
		while(tp&&a[stk[tp]]<=a[i])nxt[stk[tp--]][0]=i;
		if(i<n)stk[++tp]=i;
	}
	nxt[n][0]=n;
	for(int i=n;i>=1;i--){
		while(tp&&a[stk[tp]]<=a[i])lst[stk[tp--]][0]=i;
		if(i>1)stk[++tp]=i;
	}
	lst[1][0]=1;
//	for(int i=1;i<=n;i++)cout<<nxt[i][0]<<' ';cout<<'\n';
//	for(int i=1;i<=n;i++)cout<<lst[i][0]<<' ';cout<<'\n';
	for(int i=1;(1<<i)<=n;i++)
		for(int j=1;j+(1<<i)-1<=n;j++)
			mxlpos[i][j]=mxl(mxlpos[i-1][j],mxlpos[i-1][j+(1<<(i-1))]);
	for(int i=1;(1<<i)<=n;i++)
		for(int j=1;j+(1<<i)-1<=n;j++)
			mxrpos[i][j]=mxr(mxrpos[i-1][j],mxrpos[i-1][j+(1<<(i-1))]);
	for(int i=1;i<S;i++)
		for(int j=1;j<=n;j++)
			nxt[j][i]=max(nxt[nxt[j][i-1]][i-1],nxt[lst[j][i-1]][i-1]),
			lst[j][i]=min(lst[lst[j][i-1]][i-1],lst[nxt[j][i-1]][i-1]);
	for(int i=1,l,r;i<=q;i++){
		cin>>l>>r;
		if(l>r)swap(l,r);
		int pos=qryl(l,r),ans=qlp(l,pos)+qpr(pos,r)-1;
		int lpos=lst[qryl(l,r)][0];
		if(lpos<l)
		ans=min(ans,qpr(lpos,l)+qpr(lpos,r)-1);
		int rpos=nxt[qryr(l,r)][0];
		if(rpos>r)
		ans=min(ans,qlp(l,rpos)+qlp(r,rpos)-1);
		if(i==4&&a[2]==85){
			cout<<":"<<qlp(l,pos)+qpr(pos,r)-1<<' '<<qpr(lpos,l)+qpr(lpos,r)-1<<' '<<qlp(l,rpos)+qlp(r,rpos)-1<<'\n';
			cout<<":"<<lpos<<' '<<l<<' '<<pos<<' '<<r<<' '<<rpos<<'\n';
			cout<<":"<<a[lpos]<<' '<<a[l]<<' '<<a[pos]<<' '<<a[r]<<' '<<a[rpos]<<'\n';
			cout<<":";
			int nw=a[l];
			for(int i=l;i<=rpos;i++)if(a[i]>=nw)nw=a[i],cout<<a[i]<<' ';
			nw=a[r];
			for(int i=r;i<=rpos;i++)if(a[i]>=nw)nw=a[i],cout<<a[i]<<' ';cout<<'\n';
		}
		cout<<ans<<'\n';
	}
	return 0;
}