/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e5+100, M = 1e5+10, K = 52, MX = 30;
struct Fenwick{
vector<int> t;
Fenwick(int n){
t.resize(n + 1);
}
void add(int v){
while(v < t.size()){
t[v]++;
v += v & -v;
}
}
int get(int v){
int res=0;
while(v > 0){
res+=t[v];
v -= v&-v;
}
return res;
}
};
int n, k, q, a[N], d[N];
vector<pii> g[N];
vector<pii> A[N][21];
void solve(){
cin >> n >> k >> q;
vector<vi> C(k + 1);
for(int i = 1; i <= n; ++i){
cin >> a[i];
C[a[i]].pb(i);
}
Fenwick fw(n);
for(int i = k; i >= 1; --i){
for(int x: C[i]) fw.add(x);
for(int j = 0; j < C[i].size(); ++j){
d[C[i][j]] = fw.get(C[i][j]);
}
}
vector<pii> Q;
vector<int> W(n + 1);
int w = 1;
for(int i = 1; i <= n; ++i){
while(Q.size() && Q.back().ff <= a[i]) Q.pop_back();
if(Q.size()){
int v = i;
int u = Q.back().ss;
int last_pos = lower_bound(all(C[a[i]]), i) - C[a[i]].begin();
if(last_pos > 0 && C[a[i]][last_pos - 1] > u){
W[i] = W[C[a[i]][last_pos - 1]] + 1;
}else{
W[i] = 1;
}
// g[u].pb({v, w});
g[v].pb({u, W[i]});
}
Q.pb({a[i], i});
}
Q.clear();
w = 1;
for(int i = n; i >= 1; --i){
while(Q.size() && Q.back().ff <= a[i]) Q.pop_back();
if(Q.size()){
int v = i;
int u = Q.back().ss;
int last_pos = upper_bound(all(C[a[i]]), i) - C[a[i]].begin();
if(last_pos < C[a[i]].size() && C[a[i]][last_pos] < u){
W[i] = W[C[a[i]][last_pos]] + 1;
}else{
W[i] = 1;
}
// g[u].pb({v, w});
g[v].pb({u, W[i]});
}else
W[i] = 0;
Q.pb({a[i], i});
}
vector<bool> USED(n + 1);
for(int i = 1; i <= n; ++i){
priority_queue<pair<int, int>> Q;
Q.push({0, i});
vi use;
while(!Q.empty()){
int v = Q.top().ss;
int cur = -Q.top().ff;
Q.pop();
if(USED[v]) continue;
// if(i == 8){
// cerr << v << ' ' << cur << '\n';
// }
USED[v] = 1;
A[i][a[v]].pb({v, cur});
use.pb(v);
for(auto [u, w_]: g[v]){
Q.push({- cur - w_, u});
}
}
for(int x: use) USED[x] = 0;
// cerr <<" st" << i << '\n';
// for(int lev = 1; lev <= k; ++lev){
// for(auto [u, w]: A[i][lev]) cerr << lev << ' ' << u << ' ' << w << '\n';
// }
// cerr << "en\n";
}
for(int i = 1; i <= q; ++i){
int l, r; cin >> l >> r;
int ans = n;
for(int level = max(a[l], a[r]); level <= k; ++level){
for(auto [v, wv]: A[l][level]){
for(auto [u, wu]: A[r][level]){
// cerr << wv << ' ' << wu << ' ' << level << ' ' << u << ' ' << v << '\n';
ans = min(ans, wv + wu + d[max(u, v)] - d[min(u, v)]);
}
}
}
cout << ans - 1 << '\n';
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
en;
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
