#include <bits/stdc++.h>
#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];
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
{
    ll bit[100005];
    void init()
    {
        fill(bit, bit + N + 1, 0);
    }
    void modify(int p, ll v)
    {
        for (; p <= N; p += (p & -p))
            bit[p] += v;
    }
    ll query(int p)
    {
        ll a = 0;
        for (; p; p -= (p & -p))
            a += bit[p];
        return a;
    }
    ll bsearch(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;
    }
} blen, bcnt, bacc;

/*
 1 1 1 1 1
 5 4 3 2 1
 15 10 6 3 1
 35 20 10 4 1
 70 35 15 5 1
 126 56 21 6 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]; });

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

        if (S == 1)
        {
            for (auto &[n, k, pre, i] : qu)
                ans[i] += (pos[k] <= pre);
        }
        else if (S == 2)
        {
            int nxt = 1;
            bcnt.init();
            for (auto &[n, k, pre, i] : qu)
            {
                while (nxt <= n)
                    bcnt.modify(pos[nxt++], 1);
                ans[i] += bcnt.query(idx[i]);
            }
            sort(all(qu), [&](array<int, 4> a, array<int, 4> b) {return a[1] < b[1]; });
            nxt = 1;
            bcnt.init();
            for (auto &[n, k, pre, i] : qu)
            {
                while (nxt < k)
                    bcnt.modify(pos[nxt++], 1);
                ans[i] -= bcnt.query(idx[i]);
            }
        }
        else if (S == 3)
        {
            int nxt = 1;
            bcnt.init(), blen.init();
            for (auto &[n, k, pre, i] : qu)
            {
                while (nxt <= n)
                    bcnt.modify(pos[nxt], 1), blen.modify(pos[nxt], nxt), nxt++;
                ans[i] += blen.query(idx[i]) - bcnt.query(idx[i]) * (k - 1);
            }
            sort(all(qu), [&](array<int, 4> a, array<int, 4> b) {return a[1] < b[1]; });
            nxt = 1;
            bcnt.init(), blen.init();
            for (auto &[n, k, pre, i] : qu)
            {
                while (nxt < k)
                    bcnt.modify(pos[nxt], 1), blen.modify(pos[nxt], nxt), nxt++;
                ans[i] -= blen.query(idx[i]) - bcnt.query(idx[i]) * (k - 1);
            }
        }
        else 
        {
            int nxt = 1;
            set<int> in;
            for (auto &[n, k, pre, i] : qu)
            {
                while (nxt <= n)
                    in.insert(pos[nxt++]);
                assert(idx[i] <= 200);
                for (auto j : in)
                    if (j > idx[i]) break;
                    else 
                        ans[i] += C(p[j] - k + S - 2, S - 2);
            }
        }

        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';
    
}