# include <bits/stdc++.h>
using namespace std;
constexpr int INF=1e9;
int a[100010],nd[100010],id[200010],dep[200010],maxn[100010][20],fa[200010][20],tot=0;
vector<int> G[200010];
inline void chkmin(int &x,const int &y){x=min(x,y);}
struct Matrix
{
	int a[2][2];
	Matrix(){a[0][0]=a[0][1]=a[1][0]=a[1][1]=INF;}
	Matrix(const initializer_list<int> &L)
	{
		auto it=L.begin();
		for(int i:{0,1})
			for(int j:{0,1})
				a[i][j]=*it++;
	}
	Matrix operator*(const Matrix &t)const
	{
		Matrix ans;
		for(int i:{0,1})
			for(int j:{0,1})
				for(int k:{0,1})
					chkmin(ans.a[i][k],a[i][j]+t.a[j][k]);
		return ans;
	}
}I{0,INF,INF,0},f[200010][20];
inline int getmax(int i,int j){return a[i]!=a[j]?(a[i]>a[j]?i:j):min(i,j);}
int query(int l,int r)
{
	if(l>r) return 0;
	int k=__lg(r-l+1);
	return getmax(maxn[l][k],maxn[r-(1<<k)+1][k]);
}
int build(int l,int r)
{
	if(r-l<=1) return nd[l]=++tot;
	int u=++tot,mx=query(l+1,r-1),le=l;
	for(int i=mx;a[i]==a[mx];le=i,i=query(i+1,r-1)) G[u].push_back(build(le,i));
	G[u].push_back(build(le,r));
	return u;
}
void dfs(int u)
{
	int sz=G[u].size();
	for(int i=1;i<=16 && fa[u][i-1];i++)
	{
		fa[u][i]=fa[fa[u][i-1]][i-1];
		f[u][i]=f[fa[u][i-1]][i-1]*f[u][i-1];
	}
	for(int i=0;i<sz;i++)
	{
		int v=G[u][i];
		id[v]=i;
		f[v][0]=Matrix{i,sz-i,i+1,sz-i-1};
		dep[v]=dep[u]+1;
		fa[v][0]=u;dfs(v);
	}
}
int main()
{
	int n,m,x,y;
	scanf("%d%*d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) maxn[i][0]=i;
	for(int i=n;i;i--)
		for(int j=1;i+(1<<j)-1<=n;j++)
			maxn[i][j]=getmax(maxn[i][j-1],maxn[i+(1<<j-1)][j-1]);
	build(0,n+1);dfs(1);
	while(m--)
	{
		scanf("%d%d",&x,&y);
		if(x>y) swap(x,y);
		if(y-x<=1) puts("0");
		else
		{
			x=nd[x];y=nd[y-1];
			Matrix L=I,R=I;
			if(dep[x]>dep[y])
				for(;dep[x]>dep[y];x=fa[x][__lg(dep[x]-dep[y])])
					L=f[x][__lg(dep[x]-dep[y])]*L;
			else
				for(;dep[y]>dep[x];y=fa[y][__lg(dep[y]-dep[x])])
					R=f[y][__lg(dep[y]-dep[x])]*R;
			for(int i=16;i>=0;i--)
				if(fa[x][i]!=fa[y][i])
				{
					L=f[x][i]*L;R=f[y][i]*R;
					x=fa[x][i];y=fa[y][i];
				}
			int sz=G[fa[x][0]].size();
			printf("%d\n",min(min(L.a[1][0],L.a[1][1]+1)+min(R.a[0][0]+1,R.a[0][1])+id[y]-id[x]-1,min(L.a[0][0],L.a[0][1]+1)+min(R.a[1][0]+1,R.a[1][1])+sz+id[x]-id[y])-1);
		}
	}
	return 0;
}