// #pragma GCC target("avx2") #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include using namespace std; using P = pair; const int M = 1000000007; template class BIT { private: int n,m; vector > bit; public: // (i, j) に val を加算する void add(int i, int j, T val){ for(int i_ = i+1; i_ < n; i_ += i_ & -i_) for(int j_ = j+1; j_ < m; j_ += j_ & -j_) bit[i_][j_] += val; } // [0,i]×[0,j]の範囲の和を求める T sum(int i, int j){ T s = 0; for(int i_ = i+1; i_ > 0; i_ -= i_ & -i_) for(int j_ = j+1; j_ > 0; j_ -= j_ & -j_) s += bit[i_][j_]; return s; } // [lx, rx)×[ly, ry)の範囲の和を求める T sum(int lx, int rx, int ly, int ry){ return sum(rx-1, ry-1) - sum(lx-1, ry-1) - sum(rx-1, ly-1) + sum(lx-1, ly-1); } BIT(int sz1, int sz2){ n = sz1 + 1, m = sz2 + 1; bit.resize(n, vector(m, 0)); } BIT(vector >& v){ n = (int)v.size() + 1, m = (int)v[0].size() + 1; bit.resize(n, vector(m, 0)); for(int i = 0; i < n - 1; i++) for(int j = 0; j < m - 1; j++) add(i, j, v[i][j]); } void print(){ for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ cout<< sum(i-1, i, j-1, j) << " "; } cout << "\n"; } } void print_sum(){ for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ cout<< sum(i-1, j-1) << " "; } cout << "\n"; } } }; int main() { cin.tie(0); ios::sync_with_stdio(0); int n, k, l; cin >> n >> k >> l; vector a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } vector> ps(n + 1); for (int i = 0; i < n; ++i) { priority_queue lower; for (int j = i; j < n; ++j) { lower.push(a[j]); if ((int)lower.size() > k) lower.pop(); if ((int)lower.size() == k) { ps[lower.top()].emplace_back(i, j); } } } int q; cin >> q; vector ls(q), rs(q); for (int i = 0; i < q; ++i) { cin >> ls[i] >> rs[i]; --ls[i]; } const int MAXLOG = 12; vector ng(q, 0), ok(q, n + 1); for (int _ = 0; _ < MAXLOG; ++_) { vector> qs(n + 1); for (int i = 0; i < q; ++i) { int m = (ng[i] + ok[i]) / 2; qs[m].push_back(i); } BIT bit(n, n); for (int i = 0; i < n + 1; ++i) { for (auto& p : ps[i]) { bit.add(n - p.first - 1, p.second, 1); } for (auto& j : qs[i]) { int cnt = bit.sum(n - ls[j] - 1, rs[j] - 1); if (cnt >= l) { ok[j] = i; } else { ng[j] = i; } } } } for (auto& i : ok) { cout << i << '\n'; } return 0; }