#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;
if(k>20){
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';
}
}else{
std::vector<std::vector<int>> bylevel(k);
//std::vector<std::map<int,int>> bylevel_set(k);
std::vector<std::vector<int>> llevel(k,std::vector<int>(n)),rlevel(k,std::vector<int>(n)),linds(k,std::vector<int>(n));
for(int i=0;i<n;i++){
int x;
std::cin>>x;
x--;
levels.push_back(x);
for(int k=0;k<=x;k++)bylevel[k].push_back(i);
}
for(int i=0;i<k;i++){
int p=0;
for(int j=0;j<bylevel[i].size();j++){
linds[i][bylevel[i][j]]=j;
for(;p<=bylevel[i][j];p++){
rlevel[i][p]=bylevel[i][j];
}
}
p=n-1;
for(int j=bylevel[i].size();--j;){
for(;p>=bylevel[i][j];p--){
llevel[i][p]=bylevel[i][j];
}
}
}
for(int i=0;i<q;i++){
int a,b;
std::cin>>a>>b;
a--,b--;
if(a>b)std::swap(a,b);
int la=a,lda=0,ra=a,rda=0;
int lb=b,ldb=0,rb=b,rdb=0;
int res=1e9;
for(int j=0;j<k;j++){
if(levels[la]<j){
int nlev=llevel[j][la];
int curt=linds[j-1][la];
int nxtt=linds[j-1][nlev];
lda+=std::abs(curt-nxtt);
la=nlev;
}
if(levels[ra]<j){
int nlev=rlevel[j][ra];
int curt=linds[j-1][ra];
int nxtt=linds[j-1][nlev];
rda+=std::abs(curt-nxtt);
ra=nlev;
}
lda=std::min(rda+1,lda);rda=std::min(lda+1,rda);
if(levels[lb]<j){
int nlev=llevel[j][lb];
int curt=linds[j-1][lb];
int nxtt=linds[j-1][nlev];
ldb+=std::abs(curt-nxtt);
lb=nlev;
}
if(levels[rb]<j){
int nlev=rlevel[j][rb];
int curt=linds[j-1][rb];
int nxtt=linds[j-1][nlev];
rdb+=std::abs(curt-nxtt);
rb=nlev;
}
ldb=std::min(rdb+1,ldb);rdb=std::min(ldb+1,rdb);
res=std::min(res,ldb+rda+linds[j][lb]-linds[j][ra]);
}
std::cout<<res-1<<'\n';
}
}
}
