#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int TAILLE_MAX=100*1000+5,INFINI=1000*1000*1000;
int nbVal,typeMaxi,nbReq;
int val[TAILLE_MAX];
vector<int> posVal[TAILLE_MAX];
set<int> plusGrand;
set<int>::iterator it;
int vois[TAILLE_MAX][2];
int dist[TAILLE_MAX][2];
void calcDist(int deb,int tab) {
for (int i=1;i<=nbVal;i++) {
dist[i][tab]=INFINI;
}
deque<int> enCours;
enCours.push_back(deb);
int longueur,pos,distCour=0;
while (!enCours.empty()) {
longueur=enCours.size();
for (int i=0;i<longueur;i++) {
pos=enCours.front();
enCours.pop_front();
if (dist[pos][tab]==INFINI) {
dist[pos][tab]=distCour;
for (int j=0;j<2;j++) {
if (vois[pos][j]!=0) {
enCours.push_back(vois[pos][j]);
}
}
}
}
distCour++;
}
}
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];
posVal[val[i]].push_back(i);
}
plusGrand.insert(-INFINI);
plusGrand.insert(INFINI);
for (int i=typeMaxi;i>=1;i--) {
for (int j:posVal[i]) {
plusGrand.insert(j);
}
for (int j:posVal[i]) {
it=plusGrand.lower_bound(j);
it++;
if (abs((*it))!=INFINI) {
vois[j][1]=(*it);
}
it--;
it--;
if (abs((*it))!=INFINI) {
vois[j][0]=(*it);
}
}
}
int deb,fin,rep;
for (int ireq=0;ireq<nbReq;ireq++) {
cin>>deb>>fin;
calcDist(deb,0);
calcDist(fin,1);
rep=INFINI;
for (int i=1;i<=nbVal;i++) {
rep=min(rep,dist[i][0]+dist[i][1]);
}
cout<<rep-1<<"\n";
}
return 0;
}
