#include <bits/stdc++.h>
#ifdef CKISEKI
#define safe cerr<<__PRETTY_FUNCTION__<<" line " <<__LINE__<<" safe\n"
#define debug(a...) qwerty(#a, a)
#define orange(a...) dvorak(#a, a)
using std::cerr;
template <typename ...T>
void qwerty(const char *s, T ...a) {
    cerr << "\e[1;32m(" << s << ") = (";
    int cnt = sizeof...(T);
    (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename Iter>
void dvorak(const char *s, Iter L, Iter R) {
    cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        cerr << (f++ ? ", " : "") << *L;
    cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif

using namespace std;

const int maxn = 100025;

using Big = __int128;

struct Fenwick {
    int cnt[maxn];
    Big sum[maxn];
    void add(int p, int u, Big v) {
        for (++p; p < maxn; p += p & -p) {
            cnt[p] += u;
            sum[p] += v;
        }
    }
    pair<int,Big> query(int p) {
        int c = 0;
        Big s = 0;
        for (++p; p > 0; p -= p & -p)
            c += cnt[p], s += sum[p];
        return { c, s };
    }
    int bsearchSum(Big &k) {
        Big orgk = k;
        int p = 0;
        for (int s = 1 << 20; s; s >>= 1) {
            if (p + s < maxn && sum[p + s] < k) {
                p += s;
                k -= sum[p];
            }
        }
        if (query(p).second == orgk) {
            ++p;
            k = 0;
        }
        return p;
    }
    void init() {
        memset(cnt, 0, sizeof(cnt));
        memset(sum, 0, sizeof(sum));
    }
} BIT;

struct ar : array<Big,6> {
    ar & operator+=(const ar &rhs) {
        for (int j = 0; j < 6; j++)
            (*this)[j] += rhs[j];
        return *this;
    }
};


ar operator+(ar lhs, const ar &rhs) {
    for (int j = 0; j < 6; j++)
        lhs[j] += rhs[j];
    return lhs;
}

struct Segtree {
    ar st[maxn * 2];
    int n;
    void init(int _n) {
        n = _n;
        for (int i = 0; i < n * 2; i++)
            st[i] = ar{};
    }
    void add(int p, ar val) {
        for (st[p += n] += val; p > 1; p >>= 1)
            st[p >> 1] = st[p] + st[p ^ 1];
    }
    ar query(int l, int r) {
        ar res = {};
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res += st[l++];
            if (r & 1) res += st[--r];
        }
        return res;
    }
} sgt;

// int C(int n, int k) {
//     int64_t p = 1;
//     for (int i = 0; i < k; i++)
//         p *= n - i;
//     for (int i = 1; i <= k; i++)
//         p /= i;
//     return p;
// }

ostream & operator<<(ostream &o, Big b) {
    static auto tos = [](Big x) -> string {
        assert (x >= 0);
        if (!x) return "0";
        string s;
        while (x)
            s += char(x % 10 + '0'), x /= 10;
        reverse(s.begin(), s.end());
        return s;
    };
    return o << tos(b);
};

int main() {
    // freopen("g.in", "r", stdin);
    // cerr << "reopen g.in" << endl;
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, s, q;
    cin >> n >> s >> q;

    vector<int> p(n+1), pos(n+1);
    vector<array<Big,6>> dp(n+1);

    for (int i = 1; i <= n; i++)
        dp[i][0] = 1;

    for (int j = 1; j <= s; j++) {
        dp[0][j] = 0;
        for (int i = 1; i <= n; i++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }

    // for (int j = 0; j <= s; j++) {
    //     for (int i = 0; i <= n; i++) {
    //         cout << dp[i][j] << ' ';
    //     }
    //     cout << endl;
    // }

    // for (int i = 1; i <= n; i++) p[i] = i;
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int i = 1; i <= n; i++)
        pos[p[i]] = i;

    vector<int> ql(q);
    vector<vector<pair<Big,int>>> Q1(n+1), nQ1;
    for (int i = 0; i < q; i++) {
        int a;
        cin >> ql[i] >> a;
        Q1[n].emplace_back(a, i);
    }

    vector<vector<tuple<int,int,int>>> qs[7];
    for (int j = 0; j <= s; j++)
        qs[j].resize(n + 2);

    for (int j = s - 1; j >= 0; j--) {
        nQ1.assign(n+1, {});
        BIT.init();
        debug(j);
        for (int i = 1; i <= n; i++) {
            BIT.add(pos[i], 1, dp[i][j]);
            // for (int k = 1; k <= n; k++)
            //     cerr << BIT.query(k).second-BIT.query(k-1).second << ' ';
            // cerr << endl;

            for (auto [a, qid]: Q1[i]) {
                debug(a, qid, BIT.query(n).second);
                int pp = BIT.bsearchSum(a); // `a` changes
                // assert (ql[qid] <= i); // FIXME
                qs[j][pp].emplace_back(ql[qid], i, qid);
                if (a == 0) continue;
                int nxt = p[pp];
                nQ1[nxt].emplace_back(a, qid);
                debug(a, qid, pp, nxt);
            }
        }
        Q1 = nQ1;
    }

    vector<Big> ans(q);

    const auto calc = [](ar powsum, int a, int b) {
        // C(x - a + b, b)
        vector<Big> poly{1};
        for (int j = 0; j < b; j++) {
            // poly *= (x - a + b - j)
            vector<Big> newpoly(poly.size() + 1);
            for (int k = 0; k < poly.size(); k++) {
                newpoly[k + 1] += poly[k];
                newpoly[k] += (-a + b - j) * poly[k];
            }
            poly = newpoly;
        }

        Big res = 0;
        for (int j = 0; j < poly.size(); j++)
            res += poly[j] * powsum[j];
        return res;
    };

    for (int j = s; j >= 0; j--) {
        vector<int> freq(n + 1);
        sgt.init(n + 1);
        for (int i = 1; i <= n + 1; i++) {
            for (auto [l, r, qid]: qs[j][i]) {
                /*
                // debug(l, r, i, j);
                for (int x = 1; x < i; x++) {
                // cerr << "p[x] = " << p[x] << endl;
                if (l <= p[x] && p[x] <= r) {
                if (j == 0)
                ans[qid] += p[x] == l;
                else
                ans[qid] += C(p[x] - l + j - 1, j - 1);
                }
                }
                // debug(ans[qid]);
                 */

                if (j == 0) {
                    ans[qid] += freq[l];
                } else {
                    auto powsum = sgt.query(l, r + 1);
                    ans[qid] += calc(powsum, l, j - 1);
                }
            }
            if (i <= n) {
                freq[p[i]] += 1;
                ar tmp;
                tmp[0] = 1;
                for (int k = 1; k <= s; k++)
                    tmp[k] = tmp[k - 1] * p[i];
                sgt.add(p[i], tmp);
            }
        }
    }

    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';

    return 0;
}