#include <bits/stdc++.h>
using namespace std;
const int Nmax = 1e5 + 5, Kmax = 22;
int n, q, k;
int a[Nmax], dist[Nmax], st[Nmax];
vector<int> v[Nmax];
int goL[Nmax][Kmax], goR[Nmax][Kmax], L[Nmax][Kmax], R[Nmax][Kmax], cnt[Kmax][Nmax];
int cate(int tip, int x, int y)
{
return cnt[tip][y] - cnt[tip][x-1];
}
int walk(int x, int y)
{
if(x > y) swap(x, y);
int train = min(a[x], a[y]);
return cate(train, x+1, y);
}
int dijkstra(int x, int y)
{
queue<int> q;
int i;
for(i=1; i<=n; ++i) dist[i] = -1;
dist[x] = 0;
q.push(x);
while(q.size())
{
int node = q.front();
q.pop();
for(auto it : v[node])
if(dist[it] == -1)
{
dist[it] = dist[node] + 1;
q.push(it);
}
}
return dist[y];
}
void add_edge(int x, int y)
{
v[x].push_back(y);
v[y].push_back(x);
}
void brute()
{
int i, nr = 0;
for(i=1; i<=n; ++i)
{
while(nr && a[st[nr]] < a[i]) --nr;
if(nr) add_edge(i, st[nr]);
st[++nr] = i;
}
nr = 0;
for(i=n; i; --i)
{
while(nr && a[st[nr]] < a[i]) --nr;
if(nr) add_edge(i, st[nr]);
st[++nr] = i;
}
while(q--)
{
int x, y;
cin >> x >> y;
cout << dijkstra(x, y) - 1 << '\n';
}
}
void solve0()
{
int i, j, t;
/// sume partiale
for(i=1; i<=n; ++i)
{
for(j=1; j<=k; ++j)
cnt[j][i] = cnt[j][i-1];
for(j=a[i]; j; --j) cnt[j][i]++;
}
/// primul la stanga cu valuarea >= j
for(i=1; i<=n; ++i)
{
for(j=1; j<=k; ++j)
L[i][j] = L[i-1][j];
for(j=a[i]; j; --j) L[i][j] = i;
}
/// primul la dreapta cu valuarea >= j
for(i=n; i; --i)
{
for(j=1; j<=k; ++j)
R[i][j] = R[i+1][j];
for(j=a[i]; j; --j) R[i][j] = i;
}
/// cati pasi imi ia sa ajung in L[i][j] / R[i][j]
for(i=1; i<=k; ++i)
{
for(j=1; j<=n; ++j)
{
goL[j][i] = goR[j][i] = n+5;
if(a[j] >= i) goL[j][i] = goR[j][i] = 0;
else
{
for(t=1; t < i; ++t)
{
goL[j][i] = min(goL[j][i], walk(L[j][i], L[j][t]) + goL[j][t]);
goL[j][i] = min(goL[j][i], walk(L[j][i], R[j][t]) + goR[j][t]);
}
for(t=1; t < i; ++t)
{
goR[j][i] = min(goR[j][i], walk(R[j][i], L[j][t]) + goL[j][t]);
goR[j][i] = min(goR[j][i], walk(R[j][i], R[j][t]) + goR[j][t]);
}
}
}
}
while(q--)
{
int x, y;
cin >> x >> y;
int ans = n + 5;
for(t=1; t<=k; ++t)
{
int v1, v2, v3, v4;
v1 = goL[x][t] + goL[y][t] + walk(L[x][t], L[y][t]);
v2 = goL[x][t] + goR[y][t] + walk(L[x][t], R[y][t]);
v3 = goR[x][t] + goL[y][t] + walk(R[x][t], L[y][t]);
v4 = goR[x][t] + goR[y][t] + walk(R[x][t], R[y][t]);
ans = min(ans, v1);
ans = min(ans, v2);
ans = min(ans, v3);
ans = min(ans, v4);
}
cout << ans - 1 << '\n';
}
}
int main()
{
// freopen("input", "r", stdin);
cin.sync_with_stdio(false);
int i;
cin >> n >> k >> q;
for(i=1; i<=n; ++i) cin >> a[i];
if(q <= 50) brute();
else
if(k<=20) solve0();
return 0;
}
