#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
pii jump[100001][17];
int arr[100001];
int max_[100001][17];
int same_ind[100001];
int query(int l, int r)
{
int lg = __lg(r-l+1);
return max(max_[l][lg],max_[r-(1<<lg)+1][lg]);
}
pii do_jump(pii x, int bit)
{
return {min(jump[x.ff][bit].ff,jump[x.ss][bit].ff),max(jump[x.ff][bit].ss,jump[x.ss][bit].ss)};
}
pair<int,pii> jump_to_level(pii x, int l)
{
int ans = 0;
for(int bit = 16; bit >= 0; bit--)
{
pii new_x = do_jump(x,bit);
if(max(arr[new_x.ff],arr[new_x.ss]) < l)
{
ans += (1<<bit);
x = new_x;
}
}
if(max(arr[x.ff],arr[x.ss]) < l)
{
x = do_jump(x,0);
ans++;
}
return {ans,x};
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//random_start();
int n,k,q;
cin >> n >> k >> q;
rep2(i,1,n) cin >> arr[i];
map<int,int> cur_ind;
rep2(i,1,n) same_ind[i] = cur_ind[arr[i]]++;
rep2(i,1,n) max_[i][0] = arr[i];
rep2(bit,1,16) rep2(i,1,n) max_[i][bit] = max(max_[i][bit-1],(i+(1<<(bit-1)) <= n ? max_[i+(1<<(bit-1))][bit-1] : -1));
stack<int> st;
rep2(i,1,n)
{
while(siz(st) > 0 && arr[st.top()] < arr[i]) st.pop();
if(siz(st) == 0) jump[i][0].ff = i;
else jump[i][0].ff = st.top();
st.push(i);
}
st = {};
for(int i = n; i >= 1; i--)
{
while(siz(st) > 0 && arr[st.top()] < arr[i]) st.pop();
if(siz(st) == 0) jump[i][0].ss = i;
else jump[i][0].ss = st.top();
st.push(i);
}
rep2(bit,1,16)
{
rep2(i,1,n)
{
jump[i][bit] = do_jump(jump[i][bit-1],bit-1);
}
}
vi v1;
vi v2;
rep(qq,q)
{
int a2,b2;
cin >> a2 >> b2;
if(a2 > b2) swap(a2,b2);
pii a = {a2,a2};
pii b = {b2,b2};
int mx = query(a2,b2);
int ans = 1e9;
pair<int,pii> p1 = jump_to_level(a,mx);
pair<int,pii> p2 = jump_to_level(b,mx);
a = p1.ss;
b = p2.ss;
int max_a = -1;
if(arr[a.ff] == mx) max_a = same_ind[a.ff];
if(arr[a.ss] == mx) max_a = same_ind[a.ss];
int min_b = 1e9;
if(arr[b.ss] == mx) min_b = same_ind[b.ss];
if(arr[b.ff] == mx) min_b = same_ind[b.ff];
ans = min(ans,p1.ff+p2.ff+min_b-max_a);
a = {a2,a2};
b = {b2,b2};
p1 = jump_to_level(a,mx+1);
p2 = jump_to_level(b,mx+1);
a = p1.ss;
b = p2.ss;
v1 = {};
v2 = {};
if(arr[a.ff] > mx) v1.pb(a.ff);
if(arr[a.ss] > mx) v1.pb(a.ss);
if(arr[b.ff] > mx) v2.pb(b.ff);
if(arr[b.ss] > mx) v2.pb(b.ss);
if(siz(v1) > 0 && siz(v2) > 0)
{
int is = 1;
forall(it,v1) forall(it2,v2) if(it == it2) is = 0;
ans = min(ans,p1.ff+p2.ff+is);
}
cout << ans-1 << "\n";
}
}
