//雪花飄飄北風嘯嘯
//天地一片蒼茫
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
struct node{
int s,e,m;
int mx=0;
node *l,*r;
node (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
if (s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void update(int i,int j){
if (s==e) mx=j;
else{
if (i<=m) l->update(i,j);
else r->update(i,j);
mx=max(l->mx,r->mx);
}
}
int query(int i,int j){
if (s==i && e==j) return mx;
else if (j<=m) return l->query(i,j);
else if (m<i) return r->query(i,j);
else return max(l->query(i,m),r->query(m+1,j));
}
} *root=new node(0,100005);
int n,k,q;
int arr[100005];
vector<int> pos[100005];
int l[100005];
int r[100005];
int lp[100005];
int rp[100005];
int w[100005];
vector<ii> edges;
map<ii,int> id; //map edges to an id
//each id has 3 variants
//0 1
//0 0
//1 0
ii p[900005][20];
void process(){
vector<int> stk;
stk={};
rep(x,1,n+1){
while (!stk.empty() && arr[stk.back()]<arr[x]) stk.pob();
if (!stk.empty()) l[x]=stk.back();
stk.pub(x);
}
stk={};
rep(x,n+1,1){
while (!stk.empty() && arr[stk.back()]<arr[x]) stk.pob();
if (!stk.empty()) r[x]=stk.back();
stk.pub(x);
}
stk={};
rep(x,1,n+1){
while (!stk.empty() && arr[stk.back()]<=arr[x]) stk.pob();
if (!stk.empty()) lp[x]=stk.back();
stk.pub(x);
}
stk={};
rep(x,n+1,1){
while (!stk.empty() && arr[stk.back()]<=arr[x]) stk.pob();
if (!stk.empty()) rp[x]=stk.back();
stk.pub(x);
}
}
int nquery(int val,int l,int r){
return ub(all(pos[val]),r)-lb(all(pos[val]),l);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
cin>>n>>k>>q;
rep(x,1,n+1){
cin>>arr[x];
pos[arr[x]].pub(x);
root->update(x,arr[x]);
}
arr[0]=1e9;
process();
rep(x,1,n+1) edges.pub(ii(x,x));
rep(x,1,n+1) if (r[x] && arr[r[x]]>arr[x]) edges.pub(ii(x,r[x]));
rep(x,1,n+1) if (l[x] && arr[l[x]]>=arr[x]) edges.pub(ii(l[x],x));
sort(all(edges),[](ii i,ii j){
return (i.se-i.fi)>(j.se-j.fi);
});
memset(p,-1,sizeof(p));
rep(x,0,sz(edges)){
id[edges[x]]=x*3;
//cout<<edges[x].fi<<" "<<edges[x].se<<" "<<x*3<<endl;
int l2=edges[x].fi,r2=edges[x].se;
if (arr[l2]==k && arr[r2]==k) continue;
if (arr[l2]<arr[r2]) l2=lp[l2];
else if (arr[r2]<arr[l2]) r2=rp[r2];
else l2=lp[l2],r2=rp[r2];
int ldist=nquery(arr[edges[x].fi],l2+1,edges[x].fi);
int rdist=nquery(arr[edges[x].se],edges[x].se,r2-1);
//cout<<ldist<<" "<<rdist<<endl;
int pval=id[ii(l2,r2)];
rep(z,0,3){
int lc=0,rc=0;
if (z==0) rc=1;
if (z==2) lc=1;
lc+=ldist,rc+=rdist;
ii res;
if (lc==rc) res.fi=pval+1;
else if (lc<rc) res.fi=pval+0;
else res.fi=pval+2;
res.se=min(lc,rc);
//cout<<"parent: "<<x*3+z<<" "<<res.fi<<endl;
p[x*3+z][0]=res;
}
}
rep(it,0,sz(edges)*3){
ii curr=p[it][0];
rep(x,0,20){
if (curr.fi==-1) break;
curr.se+=p[curr.fi][x].se;
curr.fi=p[curr.fi][x].fi;
p[it][x+1]=curr;
}
}
int a,b;
while (q--){
cin>>a>>b;
if (a>b) swap(a,b);
int lo=-1;
if (a+1!=b) lo=root->query(a+1,b-1);
if (min(arr[a],arr[b])>lo){
cout<<"0"<<endl;
continue;
}
int ca=id[ii(a,a)]+1,cb=id[ii(b,b)]+1;
int da=0,db=0;
int ans;
rep(x,20,0){
if (p[ca][x].fi!=-1 && arr[edges[p[ca][x].fi/3].se]<lo){
da+=p[ca][x].se;
ca=p[ca][x].fi;
}
}
if (arr[edges[ca/3].se]<lo){
da+=p[ca][0].se;
ca=p[ca][0].fi;
}
rep(x,20,0){
if (p[cb][x].fi!=-1 && arr[edges[p[cb][x].fi/3].fi]<lo){
db+=p[cb][x].se;
cb=p[cb][x].fi;
}
}
if (arr[edges[cb/3].fi]<lo){
db+=p[cb][0].se;
cb=p[cb][0].fi;
}
ans=da+db+nquery(lo,edges[ca/3].se+1,edges[cb/3].fi-1);
if (ca%3==0) ans++;
if (cb%3==2) ans++;
if (lo!=k){
ca=id[ii(a,a)]+1,cb=id[ii(b,b)]+1;
da=0,db=0;
rep(x,20,0){
if (p[ca][x].fi!=-1 && arr[edges[p[ca][x].fi/3].fi]<=lo){
da+=p[ca][x].se;
ca=p[ca][x].fi;
}
}
if (arr[edges[ca/3].fi]<=lo){
da+=p[ca][0].se;
ca=p[ca][0].fi;
}
rep(x,20,0){
if (p[cb][x].fi!=-1 && arr[edges[p[cb][x].fi/3].se]<=lo){
db+=p[cb][x].se;
cb=p[cb][x].fi;
}
}
if (arr[edges[cb/3].se]<=lo){
db+=p[cb][0].se;
cb=p[cb][0].fi;
}
int temp=da+db;
if (ca%3==2) temp++;
if (cb%3==0) temp++;
ans=min(ans,temp);
}
cout<<ans<<endl;
}
}
