#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);
int nbVal,typeMaxi,nbReq;
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];
int voisGau[TAILLE_MAX][2],voisDro[TAILLE_MAX][2];
int distGau[TAILLE_MAX][2],distDro[TAILLE_MAX][2];
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 calcSup(int deb,int tab) {
distGau[1][tab]=0;
distDro[1][tab]=0;
voisGau[1][tab]=deb;
voisDro[1][tab]=deb;
int pos;
for (int i=2;i<=typeMaxi;i++) {
pos=voisGau[i-1][tab];
if (val[pos]<i) {
voisGau[i][tab]=supVois[pos][0];
distGau[i][tab]=distGau[i-1][tab]+distVois[pos][0];
}
else {
voisGau[i][tab]=pos;
distGau[i][tab]=distGau[i-1][tab];
}
pos=voisDro[i-1][tab];
if (val[pos]<i) {
voisDro[i][tab]=supVois[pos][1];
distDro[i][tab]=distDro[i-1][tab]+distVois[pos][1];
}
else {
voisDro[i][tab]=pos;
distDro[i][tab]=distDro[i-1][tab];
}
distGau[i][tab]=min(distGau[i][tab],distDro[i][tab]+1);
distDro[i][tab]=min(distDro[i][tab],distGau[i][tab]+1);
}
/*for (int i=1;i<=typeMaxi;i++) {
cout<<i<<" "<<voisGau[i][tab]<<" "<<distGau[i][tab]<<" "<<voisDro[i][tab]<<" "<<distDro[i][tab]<<endl;
}
cout<<endl;*/
}
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);
}
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);
}
}
}
int deb,fin,rep,hautMax;
for (int ireq=0;ireq<nbReq;ireq++) {
cin>>deb>>fin;
if (deb>fin) {
swap(deb,fin);
}
calcSup(deb,0);
calcSup(fin,1);
hautMax=1;
while (hautMax<=typeMaxi and voisDro[hautMax][0]<=voisGau[hautMax][1]) {
hautMax++;
}
if (hautMax<=typeMaxi) {
rep=min(distGau[hautMax][0]+distGau[hautMax][1],distDro[hautMax][0]+distDro[hautMax][1]);
}
else {
rep=INFINI;
}
hautMax--;
//cout<<"!"<<hautMax<<endl;
rep=min(rep,distDro[hautMax][0]+distGau[hautMax][1]+numEgau[voisGau[hautMax][1]]-numEgau[voisDro[hautMax][0]]);
cout<<rep-1<<"\n";
}
//cout<<endl;
return 0;
}
