#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)(x).size()
#define pb push_back
#define all(x) (x).begin(), (x).end()

template<typename T>
struct sparsetable {
    int n;
    vector<T> arr;
    vector<vector<T>> sp;
    function<T(T, T)> comp;
    sparsetable() = default;
    sparsetable(int n_, vector<T> arr_, function<T(T, T)> f) {
        n = n_;
        arr = arr_;
        comp = f;
        build();
    }

    void build() {
        int lg = (int) log2(n) + 1;
        sp.assign(lg, vector<T>(n));
        for (int i = 0; i < n; i++) sp[0][i] = arr[i];
        for (int i = 1; i <= lg; i++) {
            for (int j = 0; j + (1 << i) - 1 < n; j++) {
                sp[i][j] = comp(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    T get(int l, int r) {
        int lg = 31 - __builtin_clz(r - l + 1);
        return comp(sp[lg][l], sp[lg][r - (1 << lg) + 1]);
    }
};

const int LOGMAX = 17;

void solve() {
    int n, k, q; cin >> n >> k >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<pair<int, int>> b(n);
    for (int i = 0; i < n; i++) b[i] = {a[i], i};
    sparsetable<pair<int, int>> rmax(n, b, [](pair<int, int> p1, pair<int, int> p2){
        if (p1.first != p2.first) return (p1.first < p2.first ? p2 : p1);
        return (p1.second < p2.second ? p2 : p1);
    }), rmin(n, b, [](pair<int, int> p1, pair<int, int> p2){
        if (p1.first != p2.first) return (p1.first < p2.first ? p2 : p1);
        return (p1.second < p2.second ? p1 : p2);
    });

    vector<vector<int>> g(n);
    vector<int> nxt(n, -1), prv(n, -1);
    stack<int> st;
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && a[st.top()] < a[i]) st.pop();
        if (!st.empty()) {
            nxt[i] = st.top();
        }
        st.push(i);
    }
    while (!st.empty()) st.pop();
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) st.pop();
        if (!st.empty()) {
            prv[i] = st.top();
        }
        st.push(i);
    }
    vector<int> rson(n, -1), lson(n, -1);
    auto build = [&](int l, int r, int ps, auto&&self) -> void {
        if (ps < r) {
            int rp = rmin.get(ps + 1, r).second;
            rson[ps] = rp;
            g[ps].pb(rp);
            self(ps + 1, r, rp, self);
        }
        if (ps > l) {
            int lp = rmax.get(l, ps - 1).second;
            lson[ps] = lp;
            g[ps].pb(lp);
            self(l, ps - 1, lp, self);
        }
    };
    build(0, n - 1, 0, build);
    vector<int> h(n), tin(n), tout(n), par(n), jumpv(n, -1), jumpc(n);
    vector<vector<int>> up(LOGMAX, vector<int>(n));
    int tim = 0;
    auto dfs = [&](int v, auto&&self) -> void {
        tin[v] = tim++;
        up[0][v] = par[v];
        for (int i = 1; i < LOGMAX; i++) {
            up[i][v] = up[i - 1][up[i - 1][v]];
        }
        for (auto &u : g[v]) {
            par[u] = v;
            h[u] = h[v] + 1;
            self(u, self);
        }
        tout[v] = tim++;
    };
    dfs(0, dfs);
    
    auto is_par = [&](int u, int v) {
        return tin[u] <= tin[v] && tout[v] <= tout[u];
    };
    auto lca = [&](int u, int v) {
        if (is_par(u, v)) return u;
        if (is_par(v, u)) return v;
        for (int i = LOGMAX - 1; i >= 0; i--) {
            if (!is_par(up[i][u], v)) u = up[i][u];
        }
        return up[0][u];
    };

    for (int i = 0; i < n; i++) {
        if (rson[par[i]] == i && lson[par[par[i]]] == par[i]) {
            vector<int> pathr = {i};
            while (rson[pathr.back()] != -1) pathr.pb(rson[pathr.back()]);

            vector<int> used(sz(pathr), 0);
            for (int j = 0; j < sz(pathr); j++) {
                jumpv[pathr[j]] = par[par[i]];
                if (nxt[pathr[j]] == par[par[i]]) used[j] = 1;
            }
            vector<int> lind(sz(pathr), -1), rind(sz(pathr), -1);
            for (int j = 0; j < sz(pathr); j++) {
                if (j > 0) lind[j] = lind[j - 1];
                if (used[j]) lind[j] = j;
            }
            for (int j = sz(pathr) - 1; j >= 0; j--) {
                if (j < sz(pathr) - 1) rind[j] = rind[j + 1];
                if (used[j]) rind[j] = j;
            }
            for (int j = 0; j < sz(pathr); j++) {
                jumpc[pathr[j]] = j + 2;
                if (lind[j] != -1) jumpc[pathr[j]] = min(jumpc[pathr[j]], j - lind[j] + 1);
                if (rind[j] != -1) jumpc[pathr[j]] = min(jumpc[pathr[j]], rind[j] - j + 1);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if (lson[par[i]] == i && rson[par[par[i]]] == par[i]) {
            vector<int> pathr = {i};
            while (lson[pathr.back()] != -1) pathr.pb(lson[pathr.back()]);

            vector<int> used(sz(pathr), 0);
            for (int j = 0; j < sz(pathr); j++) {
                jumpv[pathr[j]] = par[par[i]];
                if (prv[pathr[j]] == par[par[i]]) used[j] = 1;
            }
            vector<int> lind(sz(pathr), -1), rind(sz(pathr), -1);
            for (int j = 0; j < sz(pathr); j++) {
                if (j > 0) lind[j] = lind[j - 1];
                if (used[j]) lind[j] = j;
            }
            for (int j = sz(pathr) - 1; j >= 0; j--) {
                if (j < sz(pathr) - 1) rind[j] = rind[j + 1];
                if (used[j]) rind[j] = j;
            }
            for (int j = 0; j < sz(pathr); j++) {
                jumpc[pathr[j]] = j + 2;
                if (lind[j] != -1) jumpc[pathr[j]] = min(jumpc[pathr[j]], j - lind[j] + 1);
                if (rind[j] != -1) jumpc[pathr[j]] = min(jumpc[pathr[j]], rind[j] - j + 1);
            }
        }
    }

    auto getd1 = [&](int v1, int v2) {
        //if (jumpv[v1] != jumpv[v2]) return (int) 1e9;
        //assert(jumpv[v1] == jumpv[v2]);
        int st = abs(h[v1] - h[v2]);
        if (jumpv[v1] != -1 && jumpv[v1] == jumpv[v2]) {
            st = min(st, jumpc[v1] + jumpc[v2]);
        }
        return st;
    };

    vector<int> ord(n);
    iota(all(ord), 0);
    sort(all(ord), [&](int i, int j){
        return h[i] < h[j];
    });
    vector<vector<int>> up_jumps(LOGMAX, vector<int>(n)), sm_jumps(LOGMAX, vector<int>(n));
    for (int v : ord) {
        up_jumps[0][v] = jumpv[v];
        sm_jumps[0][v] = jumpc[v];
        for (int i = 1; i < LOGMAX; i++) {
            up_jumps[i][v] = (up_jumps[i - 1][v] == -1 ? -1 : up_jumps[i - 1][up_jumps[i - 1][v]]);
            sm_jumps[i][v] = sm_jumps[i - 1][v] + (up_jumps[i - 1][v] == -1 ? 0 : sm_jumps[i - 1][up_jumps[i - 1][v]]);
        }
    }
    
    // for (int i = 0; i < n; i++) cout << jumpv[i] << ' ';
    // cout << '\n';
    // for (int i = 0; i < n; i++) cout << jumpc[i] << ' ';
    // cout << '\n';
    while (q--) {
        int u, v; cin >> u >> v;
        u--; v--;
        if (h[u] > h[v]) swap(u, v);
        int lc = lca(u, v);

        int S = 0;
        for (int i = LOGMAX - 1; i >= 0; i--) {
            if (up_jumps[i][u] != -1 && is_par(lc, up_jumps[i][u])) {
                S += sm_jumps[i][u];
                u = up_jumps[i][u];
            }
            if (up_jumps[i][v] != -1 && is_par(lc, up_jumps[i][v])) {
                S += sm_jumps[i][v];
                v = up_jumps[i][v];
            }
        }
        if (v == lc || u == lc) {
            cout << S + getd1(v, u) - 1 << '\n';
            continue;
        }
        int ans1 = S + min(h[u] - h[lc] + getd1(v, lc), h[v] - h[lc] + getd1(u, lc));
        if (jumpv[v] != -1) ans1 = min(ans1, S + jumpc[v] + getd1(u, jumpv[v]));
        if (jumpv[u] != -1) ans1 = min(ans1, S + jumpc[u] + getd1(jumpv[u], v));
        cout<< ans1 - 1 << '\n';
    }
}

signed main() {
    int tt = 1;
    #ifdef LOCAL 
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        cin >> tt;
    #else 
        ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    #endif

    while (tt--) {
        solve();
    }
    return 0;
}