#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
#define REP(i, n) for(int i = 0;i < n;i ++)
#define REP1(i, n) for(int i = 1;i <= n;i ++)
#define FILL(i, n) memset(i, n, sizeof(i))
#define X first
#define Y second
#define pb push_back
#define SZ(_a) ((int)(_a).size())
#define ALL(_a) (_a).begin(), (_a).end()
#ifdef brian
#define IOS()
template<typename T>void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...t>void _do(T &&x, t &&...X){cerr<<x<<", ";_do(X...);}
#define debug(...) {\
fprintf(stderr, "%s - %d (%s) = ", __PRETTY_FUNCTION__, __LINE__, #__VA_ARGS__);\
_do(__VA_ARGS__);\
}
#else
#define debug(...)
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#endif
const ll MAXn = 1e5 + 5;
const ll INF = ll(1e18);
const ll MOD = 1000000007;
ll d[MAXn], dis[MAXn], tdis[MAXn];
vector<ii> v[MAXn];
ll n, k, q;
void dijk(int s)
{
REP1(i, n)dis[i] = INF;
dis[s] = 0;
priority_queue<ii, vector<ii>, greater<ii>> pq;
pq.push(ii(0, s));
while(SZ(pq))
{
while(SZ(pq) && dis[pq.top().Y] != pq.top().X)pq.pop();
if(!SZ(pq))break;
ll t = pq.top().Y;pq.pop();
debug(t);
for(auto &p:v[t])debug(t, p.X, p.Y, dis[p.X]);
for(auto &p:v[t])if(dis[p.X] > dis[t] + p.Y)
{
debug(t, p.X);
dis[p.X] = dis[t] + p.Y;
pq.push(ii(dis[p.X], p.X));
}
}
debug(s);
REP1(i, n)debug(i, dis[i]);
}
int main(){
IOS();
cin>>n>>k>>q;
REP1(i, n)cin>>d[i];
{
vector<ll> stk;
REP1(i, n)
{
while(SZ(stk) && d[stk.back()] < d[i])stk.pop_back();
if(SZ(stk))v[i].pb(ii(stk.back(), 1));
stk.pb(i);
}
}
{
vector<ll> stk;
for(int i = n;i > 0;i --)
{
while(SZ(stk) && d[stk.back()] < d[i])stk.pop_back();
if(SZ(stk))v[i].pb(ii(stk.back(), 1));
stk.pb(i);
}
}
REP1(i, n)for(auto &p:v[i])debug(i, p.X, p.Y);
while(q--)
{
ll a, b;
cin>>a>>b;
dijk(a);
REP1(i, n)tdis[i] = dis[i];
dijk(b);
ll ans = INF;
REP1(i, n)ans = min(ans, tdis[i] + dis[i] - 1);
cout<<ans<<endl;
}
}
