#include<bits/stdc++.h>
using namespace std;
constexpr int MAX_N = 5000;
int A[MAX_N];
int compute_cnt_itr[MAX_N][MAX_N+1];
int cnt_rp[MAX_N][MAX_N+1];
int rp[MAX_N+1];
int main(){
  cin.tie(0);ios::sync_with_stdio(false);
  int N,K,L;cin >> N >> K >> L;
  for(int i=0;i<N;i++){cin >> A[i];A[i]--;}
  for(int i=0;i<N;i++){
    int k = 0;
    for(int j=0;j<N;j++){
      rp[j+1] = rp[j]+(A[j]<=i);
      while(k < N && rp[j+1]-rp[k] >= K){
        compute_cnt_itr[i][++k] = j+1;
      }
      cnt_rp[i][j+1] = cnt_rp[i][j]+k;
    }
  }
  int Q;cin >> Q;
  while(Q--){
    int l,r;cin >> l >> r;
    int ans_lef = -1,ans_rig = N-1;
    while(ans_rig - ans_lef > 1){
      int mid = (ans_lef+ans_rig)/2;
      int cnt_itr = clamp(compute_cnt_itr[mid][l],l,r+1);
      (cnt_rp[mid][r]-cnt_rp[mid][cnt_itr-1]-(r-cnt_itr+1)*(l-1) >= L ? ans_rig:ans_lef) = mid;
    }
    cout << ans_rig+1 << "\n";
  }
}