#include<bits/stdc++.h>
using namespace std;
const int MAXN = 131072;
int N, K, Q;
int L[MAXN];
enum {LEFT=0, MID=1, RIGHT=2};
struct Node
{
int l, r, p;
int pos; //position
int h; //height
int pt[3], pd[3]; //parent type, parent distance
} n[2*MAXN];
int tp = 0;
int last_left[MAXN], last_right[MAXN];
int idx[2*MAXN];
void setv(int a, int v)
{
L[a] = v;
idx[a+MAXN] = a;
a += MAXN;
while((a=a/2))
{
if(L[idx[2*a+1]] > L[idx[2*a]] ) idx[a] = idx[2*a+1];
else idx[a] = idx[2*a];
}
}
int getv(int a, int b)
{
int ans = a;
a += MAXN; b += MAXN;
while(a<=b)
{
if(a%2==1)
{
if(L[idx[a]]>L[ans]) ans = idx[a];
++a;
}
if(b%2==0)
{
if(L[idx[b]]>L[ans]) ans = idx[b];
--b;
}
a /=2; b/=2;
}
return ans;
}
vector<int> get_maxes(int from, int to)
{
vector<int> ans;
int q = getv(from, to); int qv = L[q];
ans.push_back(q);
setv(q, 0);
assert(qv != 0);
while( L[(q=getv(from, to))] == qv)
{
ans.push_back(q);
setv(q, 0);
}
sort(ans.begin(), ans.end());
for(auto x: ans) setv(x, qv);
return ans;
}
void build_rec(int id)
{
int from = n[id].l, to = n[id].r, p = id, h = n[id].h;
if(from != -1) last_left[from] = id;
if(to != N) last_right[to] = id;
if(to-from==1) return;
vector<int> child_ind = get_maxes(from+1, to-1);
for(int i=0; i<(int)child_ind.size()+1; ++i)
{
n[tp].l = (i==0)?from:child_ind[i-1];
n[tp].r = (i==(int)child_ind.size())?to:child_ind[i];
n[tp].p = p; n[tp].h = h+1; n[tp].pos = i;
for(int t=0; t<3; ++t)
{
int ldist = i; if(t==RIGHT) ++ldist;
int rdist = (int)child_ind.size()-i; if(t==LEFT) ++rdist;
if(ldist < rdist)
n[tp].pt[t] = LEFT, n[tp].pd[t] = ldist;
else if(ldist == rdist)
n[tp].pt[t] = MID, n[tp].pd[t] = ldist;
else
n[tp].pt[t] = RIGHT, n[tp].pd[t] = rdist;
}
build_rec(tp++);
}
}
int calc_dist(int aind, int atype, int bind, int btype)
{
if(aind == bind)
{
if(atype==LEFT&&btype==RIGHT) return 1;
else return 0;
}
int ans1 = n[bind].pos-n[aind].pos-1;
if(atype==LEFT) ++ans1;
if(btype==RIGHT) ++ans1;
if(n[aind].p == 0) return ans1;
return min(ans1,
n[aind].pd[atype] + n[bind].pd[btype] +
(n[aind].pt[atype] == LEFT && n[bind].pt[btype] == RIGHT)
);
}
int dist(int a, int b)
{
if(a>b) swap(a, b);
int aind = last_left[a], atype = LEFT;
int bind = last_right[b], btype = RIGHT;
int dv = 0;
while(n[aind].p != n[bind].p) //until they are sibling rel
{
if(n[aind].h < n[bind].h)
{
//take b parent
int nbind = n[bind].p;
int nbtype = n[bind].pt[btype];
dv += n[bind].pd[btype];
bind = nbind; btype = nbtype;
}
else
{
//take a parent
int naind = n[aind].p;
int natype = n[aind].pt[atype];
dv += n[aind].pd[atype];
aind = naind; atype = natype;
}
}
return calc_dist(aind, atype, bind, btype)+dv;
}
void build()
{
n[tp].l = -1; n[tp].r = N; n[tp].p = -1; n[tp].h = 0;
build_rec(tp++);
}
int main()
{
scanf("%d%d%d", &N, &K, &Q);
for(int i=0; i<N; ++i)
scanf("%d", L+i);
for(int i=0; i<N; ++i) setv(i, L[i]);
build();
while(Q--)
{
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", dist(a-1, b-1)-1);
}
}
