#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e5;
int n, k, m;
pii ranges[MAXN][20];
int heights[MAXN];
pii up_to_r(int s, int e) {
int ans = 0;
pii cur(s, s);
for (int i = 19; i >= 0; i--) {
if (max(ranges[cur.first][i].second, ranges[cur.second][i].second) < e) {
int nextl = min(ranges[cur.first][i].first, ranges[cur.second][i].first);
int nextr = max(ranges[cur.first][i].second, ranges[cur.second][i].second);
cur = pii(nextl, nextr);
ans += (1 << i);
}
}
return pii(cur.second, ans);
}
pii up_to_l(int s, int e) {
int ans = 0;
pii cur(s, s);
for (int i = 19; i >= 0; i--) {
if (min(ranges[cur.first][i].first, ranges[cur.second][i].first) > e) {
int nextl = min(ranges[cur.first][i].first, ranges[cur.second][i].first);
int nextr = max(ranges[cur.first][i].second, ranges[cur.second][i].second);
cur = pii(nextl, nextr);
ans += (1 << i);
}
}
return pii(cur.first, ans);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> k >> m;
for (int i = 0; i < n; i++) cin >> heights[i];
vector<int> q;
q.push_back(0);
ranges[0][0].first = 0;
ranges[n-1][0].second = n-1;
for (int i = 1; i < n; i++) {
while (q.size() && heights[i] >= heights[q.back()]) {
int v = q.back();
ranges[v][0].second = i;
q.pop_back();
}
q.push_back(i);
}
q.clear();
q.push_back(n-1);
for (int i = n-2; i >= 0; i--) {
while (q.size() && heights[i] >= heights[q.back()]) {
int v = q.back();
ranges[v][0].first = i;
q.pop_back();
}
q.push_back(i);
}
for (int j = 1; j < 20; j++) {
for (int i = 0; i < n; i++) {
ranges[i][j].first = min(ranges[ranges[i][j-1].first][j-1].first, ranges[ranges[i][j-1].second][j-1].first);
ranges[i][j].second = max(ranges[ranges[i][j-1].first][j-1].second, ranges[ranges[i][j-1].second][j-1].second);
}
}
for (int i = 0; i < m; i++) {
int x, y; cin >> x >> y;
x--; y--;
if (x > y) swap(x, y);
pii far_right = up_to_r(x, y);
pii far_left = up_to_l(y, far_right.first);
cout << (far_right.second+far_left.second) << "\n";
}
}
