#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


template <class T> void bAdd(vector<T> &bit, int pos, const T &val) {
  const int bitN = bit.size();
  for (int x = pos; x < bitN; x |= x + 1) bit[x] += val;
}
template <class T> T bSum(const vector<T> &bit, int pos) {
  T ret = 0;
  for (int x = pos - 1; x >= 0; x = (x & (x + 1)) - 1) ret += bit[x];
  return ret;
}
template <class T> T bSum(const vector<T> &bit, int pos0, int pos1) {
  return bSum(bit, pos1) - bSum(bit, pos0);
}

// min pos s.t. pred(sum of [0, pos))
//   assume pred(sum of [0, pos)) is non-decreasing
template <class T, class Pred>
int bBinarySearch(const vector<T> &bit, Pred pred) {
  if (pred(T(0))) return 0;
  const int bitLen = bit.size();
  int pos = 0;
  T sum = 0;
  for (int e = 31 - __builtin_clz(bitLen); e >= 0; --e) {
    const int x = (pos | 1 << e) - 1;
    if (x < bitLen && !pred(sum + bit[x])) {
      pos |= 1 << e;
      sum += bit[x];
    }
  }
  return pos + 1;
}


constexpr Int INF = 1001001001001LL;

/*
  expand p
  count k
  prefix (0, a]
*/
struct Query {
  int p;
  int k;
  Int a;
};

int N, S, Q;
vector<int> P;
vector<int> K;
vector<Int> A;

// len from (s, p)
Int lss[6][100'010];

__int128 bit[100'010][6];

int main() {
  __int128 fs[6];
  
  for (; ~scanf("%d%d%d", &N, &S, &Q); ) {
    P.assign(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
      scanf("%d", &P[i]);
    }
    K.resize(Q);
    A.resize(Q);
    for (int q = 0; q < Q; ++q) {
      scanf("%d%lld", &K[q], &A[q]);
    }
    
    fill(lss[0] + 1, lss[0] + (N + 1), 1);
    for (int s = 1; s <= S; ++s) {
      for (int n = 1; n <= N; ++n) {
        lss[s][n] = min(lss[s][n - 1] + lss[s - 1][n], INF);
      }
// cerr<<"lss["<<s<<"] = ";pv(lss[s],lss[s]+N+1);
    }
    
    vector<int> invP(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
      invP[P[i]] = i;
    }
    
    vector<Int> ans(Q, 0);
    vector<Query> qrys(Q);
    for (int q = 0; q < Q; ++q) {
      qrys[q] = {N, K[q], A[q]};
    }
    // s+1 -> s
    for (int s = S; --s >= 0; ) {
// cerr<<"s = "<<s<<endl;
      vector<int> is(Q);
      vector<vector<pair<int, int>>> events(N + 1);
      {
        vector<vector<int>> qss(N + 1);
        for (int q = 0; q < Q; ++q) {
          qss[qrys[q].p].push_back(q);
        }
        vector<Int> bitL(N + 1);
        for (int p = 1; p <= N; ++p) {
// cerr<<"  add p="<<p<<" at "<<invP[p]<<"; "<<lss[s][p]<<endl;
          bAdd(bitL, invP[p], lss[s][p]);
          for (const int q : qss[p]) {
            is[q] = bBinarySearch(bitL, [&](Int l) -> bool {
              return (l >= qrys[q].a);
            }) - 1;
// cerr<<"  is["<<q<<"] = "<<is[q]<<endl;
            assert(is[q] <= N);
            const int k = qrys[q].k;
            if (k <= p) {
              if (s == 0) {
                if (invP[k] <= is[q]) {
                  ans[q] += 1;
                }
              } else {
                events[k].emplace_back(q, +1);
                if (p + 1 <= N) {
                  events[p + 1].emplace_back(q, -1);
                }
              }
            }
            qrys[q].p = P[is[q]];
            qrys[q].a -= bSum(bitL, is[q]);
          }
        }
      }
      if (s >= 1) {
        for (int i = 0; i <= N; ++i) {
          fill(bit[i], bit[i] + s, 0);
        }
        for (int j = N; j >= 1; --j) {
          /*
            multichoose(s, j - X)
            = binom(s + j - X - 1, s - 1)
          */
          Int denom = 1;
          fill(fs, fs + s, 0);
          fs[0] = 1;
          for (int h = 0; h < s - 1; ++h) {
            denom *= (1 + h);
            // *= (-X + s+j-1 - h)
            for (int d = h; d >= 0; --d) {
              fs[d + 1] -= fs[d];
              fs[d] *= (s + j - 1 - h);
            }
          }
// cerr<<"  j = "<<j<<"; fs = ";pv(fs,fs+s);
          for (int x = invP[j]; x < N + 1; x |= x + 1) {
            for (int d = 0; d < s; ++d) {
              bit[x][d] += fs[d];
            }
          }
          for (const auto &event : events[j]) {
            const int q = event.first;
            const int k = qrys[q].k;
            // X = k
            fill(fs, fs + s, 0);
            for (int x = is[q]; x > 0; x &= x - 1) {
              for (int d = 0; d < s; ++d) {
                fs[d] += bit[x - 1][d];
              }
            }
            __int128 val = 0;
            for (int d = s; --d >= 0; ) {
              (val *= k) += fs[d];
            }
            val /= denom;
            ans[q] += event.second * val;
          }
        }
      }
// cerr<<"ans = "<<ans<<endl;
    }
    
    for (int q = 0; q < Q; ++q) {
      printf("%lld\n", ans[q]);
    }
#ifdef LOCAL
vector<int>crt{N};
for(int s=0;s<S;++s){
 vector<int>nxt;
 for(const int j:crt)for(int i=1;i<=N;++i)if(P[i]<=j)nxt.push_back(P[i]);
 crt=nxt;
}
vector<Int>brt(Q,0);
for(int q=0;q<Q;++q){
 assert(A[q]<=(int)crt.size());
 for(int a=0;a<A[q];++a)if(crt[a]==K[q])++brt[q];
}
if(brt!=ans){
 cerr<<"N = "<<N<<", S = "<<S<<", Q = "<<Q<<endl;
 cerr<<"P = "<<P<<endl;
 cerr<<"K = "<<K<<endl;
 cerr<<"A = "<<A<<endl;
 cerr<<"brt = "<<brt<<endl;
 cerr<<"ans = "<<ans<<endl;
}
assert(brt==ans);
#endif
  }
  return 0;
}