//STRIKER!
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <iomanip>
#include <numeric>
#include <random>
#include <chrono>
using namespace std;
//#define int int64_t //uint64_t
#define pb push_back
#define perfectblue cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
#define all(a) a.begin(), a.end()
#define sz(a) ((int)a.size())
const int maxn = 2e5 + 10;
const int LOG = 19;
int n, k, q;
int a[maxn];
int L[maxn];
int R[maxn];
int spl[LOG + 1][maxn];
int spr[LOG + 1][maxn];
void sol() {
cin >> n >> k >> q;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
stack<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() and a[st.top()] < a[i]) {
st.pop();
}
L[i] = (!st.empty() ? st.top() : i);
st.push(i);
}
while (!st.empty()) {
st.pop();
}
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() and a[st.top()] < a[i]) {
st.pop();
}
R[i] = (!st.empty() ? st.top() : i);
st.push(i);
}
for (int i = 0; i < n; i++) {
spl[0][i] = L[i];
spr[0][i] = R[i];
}
for (int k = 1; k <= LOG; k++) {
for (int i = 0; i < n; i++) {
int l = spl[k - 1][i];
int r = spr[k - 1][i];
spl[k][i] = min(spl[k - 1][l], spl[k - 1][r]);
spr[k][i] = max(spr[k - 1][l], spr[k - 1][r]);
}
}
while (q--) {
int a, b;
cin >> a >> b;
a--, b--;
if (a > b) {
swap(a, b);
}
int l = a;
int r = a;
int ans = 0;
for (int k = LOG; k >= 0; k--) {
if (max(spr[k][l], spr[k][r]) < b) {
ans += (1 << k);
int ll = l;
int rr = r;
l = min(spl[k][ll], spl[k][rr]);
r = max(spr[k][ll], spr[k][rr]);
}
}
a = r;
l = b;
r = b;
for (int k = LOG; k >= 0; k--) {
if (min(spl[k][l], spl[k][r]) > a) {
ans += (1 << k);
int ll = l;
int rr = r;
l = min(spl[k][ll], spl[k][rr]);
r = max(spr[k][ll], spr[k][rr]);
}
}
cout << ans << "\n";
}
}
int32_t main() {
perfectblue;
int t = 1;
//cin >> t;
while (t--) {
sol();
}
return 0;
}
//freopen("name", "r", stdin);
//freopen("name", "w", stdout);
