#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second 
#define all(x) x.begin(), x.end()

using namespace std;

const ll INF = 1e13;
int N, S, Q, p[100005], pos[100005], idx[200005];
unsigned ll ans[200005];

ll C(ll n, ll k)
{
    if (k > n) return 0;
    ll a = 1;
    for (int i = 0; i < k; i++)
        a = min(a * (n - i), INF);
    for (int i = 1; i <= k; i++)
        a /= i;
    return a;
}

struct BIT
{
    unsigned ll bit[100005];
    void init()
    {
        fill(bit, bit + N + 1, 0);
    }
    void modify(int p, unsigned ll v)
    {
        for (; p <= N; p += (p & -p))
            bit[p] += v;
    }
    unsigned ll query(int p)
    {
        ll a = 0;
        for (; p; p -= (p & -p))
            a += bit[p];
        return a;
    }
    unsigned ll bsearch(unsigned ll v)
    {
        ll r = 0;
        for (int p = (1 << __lg(N)); p >= 1; p >>= 1)
            if (r + p <= N && bit[r + p] < v)
                v -= bit[r + p], r += p;
        return r;
    }
} bcnt[4], bacc;

/*
 1 1 1 1
 4 3 2 1
 10 6 3 1
 20 10 4 1
// s = 1: count number
// s = 2: count 
// s >= 3: brute 
*/

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    cin >> N >> S >> Q;

    // #ifdef debug
    // cerr << "debug mode!\n";
    // vector<int> v(N);
    // iota(all(v), 1);
    // mt19937 rd(1);
    // shuffle(all(v), rd);
    // stringstream cin;
    // for (int i = 0; i < N; i++)
    //     cin << v[i] << ' ';
    // for (int i = 1; i <= Q; i++)
    //     cin << rd() % N + 1 << ' ' << rd() % 1'000'000'000 + 1 << ' ';
    // cerr << "debug mode end!\n";
    // stringstream cout;
    // #endif

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

    // every query is in the form (n, pos, k, i)
    vector<array<int, 4>> qu;
    for (int i = 1; i <= Q; i++)
    {
        int len, k;
        cin >> k >> len;
        qu.emplace_back(array{N, k, len, i});
    }
    for (; S >= 1; S--)
    {
        vector<array<int, 4>> nqu;
        sort(all(qu), [&](array<int, 4> a, array<int, 4> b) {return a[0] < b[0]; });

        {    
            ll nxt = 1;
            bacc.init();
            for (auto &[n, k, len, i] : qu)
            {
                while (nxt <= n)
                    bacc.modify(pos[nxt], C(nxt + S - 2, S - 1)), nxt++;
                idx[i] = (int)bacc.bsearch(len);
                len -= bacc.query(idx[i]);
            }
        }

        if (S == 1)
        {
            for (auto &[n, k, pre, i] : qu)
                ans[i]++;
        }
        else
        {
            ll nxt = 1;
            bcnt[0].init(), bcnt[1].init(), bcnt[2].init(), bcnt[3].init();
            for (auto &[n, k, pre, i] : qu)
            {
                while (nxt <= n)
                {    
                    bcnt[0].modify(pos[nxt], 1);
                    bcnt[1].modify(pos[nxt], nxt);
                    bcnt[2].modify(pos[nxt], nxt * nxt);
                    bcnt[3].modify(pos[nxt], nxt * nxt * nxt);
                    nxt++;
                }
                if (S == 2)
                    ans[i] += bcnt[0].query(idx[i]);
                else if (S == 3) // (n - k)
                    ans[i] += 1 *           bcnt[1].query(idx[i]) +
                              -(k - 1) *    bcnt[0].query(idx[i]);
                else if (S == 4) // (n - k)^2 = n^2 - 2nk + k^2
                    ans[i] += 1 *                   bcnt[2].query(idx[i]) +
                              -(2 * k - 2) *        bcnt[1].query(idx[i]) +
                              +(k - 1) *(k - 1) *   bcnt[0].query(idx[i]);
                else if (S == 5) // (n - k)^3 = n^3 - 3n^2k + 3nk^2 - k^3
                    ans[i] += 1 *                   bcnt[3].query(idx[i]) +
                              -(3 * k - 3) *        bcnt[2].query(idx[i]) +
                              +3*(k - 1) *(k - 1) *   bcnt[1].query(idx[i]) +
                              -(k - 1) *(k - 1) *(k - 1) *   bcnt[0].query(idx[i]);
            }
            sort(all(qu), [&](array<int, 4> a, array<int, 4> b) {return a[1] < b[1]; });
            nxt = 1;
            bcnt[0].init(), bcnt[1].init(), bcnt[2].init(), bcnt[3].init();
            for (auto &[n, k, pre, i] : qu)
            {
                while (nxt < k)
                {    
                    bcnt[0].modify(pos[nxt], 1);
                    bcnt[1].modify(pos[nxt], nxt);
                    bcnt[2].modify(pos[nxt], nxt * nxt);
                    bcnt[3].modify(pos[nxt], nxt * nxt * nxt);
                    nxt++;
                }
                if (S == 2)
                    ans[i] -= bcnt[0].query(idx[i]);
                else if (S == 3) // (n - k)
                    ans[i] -= 1 *           bcnt[1].query(idx[i]) +
                              -(k - 1) *    bcnt[0].query(idx[i]);
                else if (S == 4) // (n - k)^2 = n^2 - 2nk + k^2
                    ans[i] -= 1 *                   bcnt[2].query(idx[i]) +
                              -(2 * k - 2) *        bcnt[1].query(idx[i]) +
                              +(k - 1) *(k - 1) *   bcnt[0].query(idx[i]);
                else if (S == 5) // (n - k)^3 = n^3 - 3n^2k + 3nk^2 - k^3
                    ans[i] -= 1 *                   bcnt[3].query(idx[i]) +
                              -(3 * k - 3) *        bcnt[2].query(idx[i]) +
                              +3*(k - 1) *(k - 1) *   bcnt[1].query(idx[i]) +
                              -(k - 1) *(k - 1) *(k - 1) *   bcnt[0].query(idx[i]);
            }
        }

        for (auto &[n, k, pre, i] : qu)
        {
            if (idx[i] == N || p[idx[i] + 1] < k)
                continue;
            else 
            {    
                tie(n, k, pre) = make_tuple(p[idx[i] + 1], k, pre);
                nqu.emplace_back(array{n, k, pre, i});
            }
        }
        nqu.swap(qu);
    }
    for (int i = 1; i <= Q; i++)
        cout << ans[i] << '\n';
    
}