#include<bits/stdc++.h>
using namespace std;
#define int long long
const int TAILLE_MAX=100*1000+5,INFINI=1000*1000*1000,DECA=(1<<17),MAX_INTER=900*1000+5,MAX_LOG=20;
int nbVal,typeMaxi,nbReq,nbInter;
int val[TAILLE_MAX];
vector<int> posVal[TAILLE_MAX];
set<int> plusGrand;
set<int>::iterator it;
int supVois[TAILLE_MAX][2];
int distVois[TAILLE_MAX][2];
int numEgau[TAILLE_MAX];
int arbreSom[2*DECA];
vector<pair<int,int>> interInteress;
unordered_map<int,int> corres;
int suiv[MAX_INTER][MAX_LOG][2];
int hautInter[MAX_INTER];
int hache(int deb,int fin) {
return deb*TAILLE_MAX+fin;
}
void ajout(int pos) {
pos+=DECA;
while (pos>0) {
arbreSom[pos]++;
pos/=2;
}
}
int calcInter(int deb,int fin) {
if (deb==fin) {
return arbreSom[deb];
}
if (deb%2==1) {
return arbreSom[deb]+calcInter(deb+1,fin);
}
if (fin%2==0) {
return arbreSom[fin]+calcInter(deb,fin-1);
}
return calcInter(deb/2,fin/2);
}
void calcSuiv(int deb,int fin,int diff) {
int distGau=0,distDro=0,caseTab=corres[hache(deb,fin)]+nbInter*diff;
hautInter[caseTab]=min(val[deb],val[fin]);
if (diff==0) {
distGau=1;
}
else if (diff==2) {
distDro=1;
}
int voisGau=deb,voisDro=fin,pos,hautSuiv=min(val[deb],val[fin])+1;
//cout<<caseTab<<" ";
if (hautSuiv>typeMaxi) {
//cout<<"#"<<caseTab%nbInter<<" ";
suiv[caseTab][0][0]=caseTab;
suiv[caseTab][0][1]=0;
}
else {
pos=voisGau;
if (val[pos]<hautSuiv) {
voisGau=supVois[pos][0];
distGau+=distVois[pos][0];
}
pos=voisDro;
if (val[pos]<hautSuiv) {
voisDro=supVois[pos][1];
distDro+=distVois[pos][1];
}
distGau=min(distGau,distDro+1);
distDro=min(distDro,distGau+1);
int suivDiff,minDist=min(distGau,distDro);
distGau-=minDist;
distDro-=minDist;
if (distGau==1 and distDro==0) {
suivDiff=0;
}
else if (distGau==0 and distDro==0) {
suivDiff=1;
}
else {
suivDiff=2;
}
suiv[caseTab][0][0]=corres[hache(voisGau,voisDro)]+nbInter*suivDiff;
suiv[caseTab][0][1]=minDist;
}
}
pair<int,int> findInter(int pos,int hautMax) {
if (hautInter[pos]>=hautMax) {
return {pos,0};
}
int distParc=0;
for (int i=MAX_LOG-1;i>=0;i--) {
if (hautInter[suiv[pos][i][0]]<hautMax) {
distParc+=suiv[pos][i][1];
pos=suiv[pos][i][0];
}
}
distParc+=suiv[pos][0][1];
pos=suiv[pos][0][0];
return {pos,distParc};
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>nbVal>>typeMaxi>>nbReq;
for (int i=1;i<=nbVal;i++) {
cin>>val[i];
numEgau[i]=posVal[val[i]].size();
posVal[val[i]].push_back(i);
interInteress.push_back({i,i});
}
plusGrand.insert(-INFINI);
plusGrand.insert(INFINI);
for (int i=typeMaxi;i>=1;i--) {
for (int j:posVal[i]) {
it=plusGrand.lower_bound(j);
if (abs((*it))!=INFINI) {
supVois[j][1]=(*it);
}
it--;
if (abs((*it))!=INFINI) {
supVois[j][0]=(*it);
}
}
for (int j:posVal[i]) {
plusGrand.insert(j);
ajout(j);
}
for (int j:posVal[i]) {
if (supVois[j][0]!=0) {
distVois[j][0]=calcInter(DECA+1,DECA+j)-calcInter(DECA+1,DECA+supVois[j][0]);
}
if (supVois[j][1]!=0) {
distVois[j][1]=calcInter(DECA+1,DECA+supVois[j][1])-calcInter(DECA+1,DECA+j);
}
it=plusGrand.lower_bound(j);
it++;
if (abs((*it))!=INFINI and val[(*it)]>i) {
interInteress.push_back({j,abs(*it)});
}
it--;
it--;
if (abs((*it))!=INFINI) {
interInteress.push_back({abs(*it),j});
}
}
}
//cout<<interInteress.size()<<endl;
nbInter=interInteress.size();
for (int i=0;i<nbInter;i++) {
//cout<<interInteress[i].first<<" "<<interInteress[i].second<<endl;
corres[hache(interInteress[i].first,interInteress[i].second)]=i;
}
for (int i=0;i<nbInter;i++) {
for (int j=0;j<3;j++) {
calcSuiv(interInteress[i].first,interInteress[i].second,j);
}
//cout<<interInteress[i].first<<" "<<interInteress[i].second<<" : "<<interInteress[suiv[i][0][0]%nbInter].first<<" "<<interInteress[suiv[i][0][0]%nbInter].second<<endl;
}
for (int j=1;j<MAX_LOG;j++) {
for (int i=0;i<3*nbInter;i++) {
suiv[i][j][0]=suiv[suiv[i][j-1][0]][j-1][0];
suiv[i][j][1]=suiv[i][j-1][1]+suiv[suiv[i][j-1][0]][j-1][1];
}
}
int deb,fin,rep,hautMax,debDicho,finDicho,midDicho;
pair<int,int> interGau,interDro;
for (int ireq=0;ireq<nbReq;ireq++) {
cin>>deb>>fin;
if (deb>fin) {
swap(deb,fin);
}
debDicho=max(val[deb],val[fin])+1;
finDicho=typeMaxi+1;
while (debDicho!=finDicho) {
midDicho=(debDicho+finDicho)/2;
interGau=findInter(corres[hache(deb,deb)]+nbInter,midDicho);
interDro=findInter(corres[hache(fin,fin)]+nbInter,midDicho);
if (interGau.first%nbInter==interDro.first%nbInter) {
finDicho=midDicho;
}
else {
debDicho=midDicho+1;
}
}
hautMax=debDicho;
if (hautMax<=typeMaxi) {
interGau=findInter(corres[hache(deb,deb)]+nbInter,hautMax);
interDro=findInter(corres[hache(fin,fin)]+nbInter,hautMax);
rep=interGau.second+interDro.second+min((interGau.first/nbInter==0)+(interDro.first/nbInter==0),
(interGau.first/nbInter==2)+(interDro.first/nbInter==2));
}
else {
rep=INFINI;
}
//cout<<"!"<<hautMax-1<<" "<<rep<<endl;
interGau=findInter(corres[hache(deb,deb)]+nbInter,hautMax-1);
interDro=findInter(corres[hache(fin,fin)]+nbInter,hautMax-1);
rep=min(rep,interGau.second+(interGau.first/nbInter==2)+interDro.second+(interDro.first/nbInter==0)+
numEgau[interInteress[interDro.first%nbInter].first]-numEgau[interInteress[interGau.first%nbInter].second]);
/*if (rep<=0) {
cout<<deb<<" "<<fin<<endl;
}*/
cout<<rep-1<<"\n";
}
//cout<<endl;
return 0;
}
