#include <bits/stdc++.h>
/*
20p: just Dijkstra
45p: keep left/right for each level (impossible to go past them)
Cartesian tree-like
Square root?
*/
int main(){
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::vector<int> levels;
int n,k,q;
std::cin>>n>>k>>q;
std::vector<std::vector<int>> edges(n);
std::vector<std::vector<int>> bylevel(k);
std::set<int> nums;
for(int i=0;i<n;i++){
int x;
std::cin>>x;
x--;
levels.push_back(x);
bylevel[x].push_back(i);
}
for(int i=k;i--;){
for(int j=0;j<bylevel[i].size();j++){
nums.insert(bylevel[i][j]);
}
for(int j=0;j<bylevel[i].size();j++){
if(bylevel[i][j]!=0)edges[bylevel[i][j]].push_back(*--nums.lower_bound(bylevel[i][j]));
if(bylevel[i][j]!=n-1)edges[bylevel[i][j]].push_back(*nums.upper_bound(bylevel[i][j]));
//std::cout<<edges[bylevel[i][j]][0]<<'\n';
}
}
for(int i=0;i<q;i++){
int a,b;
std::cin>>a>>b;
a--,b--;
std::vector<int> dists1(n,1e9),dists2(n,1e9);
std::priority_queue<std::pair<int,int>> dijkstra;
dijkstra.push({-0,a});
while(!dijkstra.empty()){
std::pair<int,int> cur=dijkstra.top();
dijkstra.pop();
if(dists1[cur.second]<=-cur.first)continue;
dists1[cur.second]=-cur.first;
for(int i:edges[cur.second]){
dijkstra.push({cur.first-1,i});
}
}
dijkstra.push({-0,b});
while(!dijkstra.empty()){
std::pair<int,int> cur=dijkstra.top();
dijkstra.pop();
if(dists2[cur.second]<=-cur.first)continue;
dists2[cur.second]=-cur.first;
for(int i:edges[cur.second]){
dijkstra.push({cur.first-1,i});
}
}
int mndst=1e9;
for(int j=0;j<n;j++){
//std::cout<<dists1[j]+dists2[j]<<'\n';
mndst=std::min(mndst,dists1[j]+dists2[j]);
}
std::cout<<mndst-1<<'\n';
}
}
