#include <bits/stdc++.h>
#include <cassert>

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;
    //cout << n << ' ' << k << ' ' << q  << '\n';
    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), g2(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();
            g2[i].pb(nxt[i]);
            g2[nxt[i]].pb(i);
        }
        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();
            g2[i].pb(prv[i]);
            g2[prv[i]].pb(i);
        }
        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);
            g[rp].pb(ps);
            self(ps + 1, r, rp, self);
        }
        if (ps > l) {
            int lp = rmax.get(l, ps - 1).second;
            lson[ps] = lp;
            g[ps].pb(lp);
            g[lp].pb(ps);
            self(l, ps - 1, lp, self);
        }
    };
    build(0, n - 1, 0, build);
    
    vector<vector<pair<int, int>>> qrs(n);
    vector<pair<int, int>> Q(q);
    for (int i = 0; i < q; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        Q[i] = {u, v};
        qrs[u].pb({v, i});
        qrs[v].pb({u, i});
    }
    vector<int> ans(q, n + 1);
    //cout << ans.size() << '\n';
    vector<int> tin(n), tout(n), h(n);
    int timer = 0;
    auto dfs = [&](int v, int p, auto&&self) -> void {
        tin[v] = timer++;
        for (int u : g[v]) {
            if (u != p) {
                h[u] = h[v] + 1;
                self(u, v, self);
            }
        }
        tout[v] = timer++;
    };
    dfs(0, 0, dfs);
    auto is_par = [&](int v1, int v2) {
        return tin[v1] <= tin[v2] && tout[v2] <= tout[v1];
    };
    
    vector<int> used_cent(n), need_find(n), siz(n), used(n);
    vector<vector<int>> cent_cmp(n);
    need_find[0] = 1;
    int cur = 1, step = 0;
    vector<int> curcmp;
    auto dfs_siz = [&](int v, auto&&self) -> void {
        siz[v] = 1; used[v] = step; curcmp.pb(v);
        for (int u : g[v]) {
            if (used[u] != step && !used_cent[u]) {
                self(u, self);
                siz[v] += siz[u];
            }
        }
    };
    auto find_cent = [&](int v, int init_size, auto&&self) -> int {
        used[v] = step;
        for (int u : g[v]) {
            if (used[u] != step && !used_cent[u] && siz[u] > init_size / 2) return self(u, init_size, self);
        }
        return v;
    };
    while (true) {
        bool allgood = true;
        for (int i = 0; i < n; i++) {
            if (need_find[i] == cur) {
                curcmp.clear();
                allgood = false;
                step++; dfs_siz(i, dfs_siz); step++;
                int vt = find_cent(i, siz[i], find_cent);
                //cout << i << ' ' << cur << ' ' << vt << '\n';
                used_cent[vt] = 1;
                cent_cmp[vt] = curcmp;
                for (int u : g[vt]) {
                    if (!used_cent[u]) need_find[u] = cur + 1;
                }
            }
        }
        if (allgood) break;
        cur++;
    }
    vector<int> pos(n);
    for (int i = 0; i < n; i++) {
        // cout << i << endl;
        // for (int u : cent_cmp[i]) cout << u << ' ';
        // cout << endl;
        step++;
        for (int u : cent_cmp[i]) used[u] = step;
        vector<int> curq;
        for (int u : cent_cmp[i]) {
            for (auto [v, num] : qrs[u]) {
                if (v > u && used[v] == step) curq.pb(num);
            }
        }
        unordered_set<int> roots;
        roots.insert(i);
        for (int u : cent_cmp[i]) {
            if (u != i && nxt[u] != -1 &&  is_par(i, u) && is_par(nxt[u], i) && used[nxt[i]] == step) {
                roots.insert(nxt[u]);
            }
            if (u != i && prv[u] != -1 && is_par(i, u) && is_par(prv[u], i) && used[prv[i]] == step) {
                roots.insert(prv[u]);
            }
        }
        for (int j = 0; j < cent_cmp[i].size(); j++) pos[cent_cmp[i][j]] = j;
        vector<vector<int>> newg(sz(cent_cmp[i]));
        for (int j = 0; j < cent_cmp[i].size(); j++) {
            for (int u : g2[cent_cmp[i][j]]) {
                if (used[u] == step) newg[j].pb(pos[u]);
            }
        }
        for (int rt : roots) {
            vector<int> dist(sz(cent_cmp[i]), -1);
            //assert(rt == i || used[rt] == step);
            dist[pos[rt]] = 0;
            queue<int> q;
            q.push(pos[rt]);
            while (!q.empty()) {
                int V = q.front();
                q.pop();
                for (int u : newg[V]) {
                    if (dist[u] == -1) {
                        dist[u] = dist[V] + 1;
                        q.push(u);
                    }
                }
            }
            for (int qnum : curq) {
                ans[qnum] = min(ans[qnum], dist[pos[Q[qnum].first]] + dist[pos[Q[qnum].second]]);
            }
        }
    }
    //cout << sz(ans) << '\n';
    for (int el : ans) cout << el - 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;
}