#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k, q;
    cin >> n >> k >> q;

    const int lg = __lg(n) + 1;

    vector<int> h(n), stk;
    vector l(lg, vector<int>(n)), r(lg, vector<int>(n, n - 1));

    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }

    for (int i = 0; i < n; ++i) {
        while (!stk.empty() && h[stk.back()] < h[i]) {
            r[0][stk.back()] = i;
            stk.pop_back();
        }
        if (!stk.empty()) {
            l[0][i] = stk.back();
            if (h[stk.back()] == h[i]) {
                r[0][stk.back()] = i;
                stk.pop_back();
            }
        }
        stk.push_back(i);
    }

    for (int i = 1; i < lg; ++i) {
        for (int x = 0; x < n; ++x) {
            int lx = l[i - 1][x], rx = r[i - 1][x];
            l[i][x] = min(l[i - 1][lx], l[i - 1][rx]);
            r[i][x] = max(r[i - 1][lx], r[i - 1][rx]);
        }
    }

    for (int qwq = 0; qwq < q; ++qwq) {
        int a, b;
        cin >> a >> b;
        a -= 1, b -= 1;
        if (a > b) {
            swap(a, b);
        }

        int ans = 0;
        int lx = a, rx = a;

        for (int i = lg - 1; i >= 0; --i) {
            int la = min(l[i][lx], l[i][rx]), ra = max(r[i][lx], r[i][rx]);
            if (ra < b) {
                ans += 1 << i;
                lx = la, rx = ra;
            }
        }

        a = rx;
        lx = b, rx = b;

        for (int i = lg - 1; i >= 0; --i) {
            int lb = min(l[i][lx], l[i][rx]), rb = max(r[i][lx], r[i][rx]);
            if (lb > a) {
                ans += 1 << i;
                lx = lb, rx = rb;
            }
        }

        cout << ans << '\n';
    }

    return 0;
}