#pragma GCC target("avx2") #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include using namespace std; using P = pair; const int M = 1000000007; 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> kth(n + 1, vector(n + 1, M)); for (int i = 0; i < n + 1; ++i) { for (int l = 0, r = 0, c = 0; l < n; ++l) { while (r < n && c < K) { if (a[r] <= i) ++c; ++r; } if (c == K) { kth[l][r] = min(kth[l][r], i); } else break; if (a[l] <= i) --c; } } for (int d = 1; d <= n; ++d) { for (int i = 0; i + d <= n; ++i) { kth[i][i + d] = min(kth[i][i + d], min(kth[i + 1][i + d], kth[i][i + d - 1])); } } vector> cnth(n + 1, vector(n + 1)); vector> cntw(n + 1, vector(n + 1)); for (int i = 0; i < n + 1; ++i) { for (int j = 0; j < n + 1; ++j) { if (kth[i][j] != M) { ++cnth[i][kth[i][j]]; ++cntw[j][kth[i][j]]; } } } for (int i = 0; i < n + 1; ++i) { for (int j = 0; j < n; ++j) { cnth[i][j + 1] += cnth[i][j]; cntw[i][j + 1] += cntw[i][j]; } } vector> lth(n + 1, vector(n + 1, M)); for (int i = 0; i < n + 1; ++i) { for (int l = 0, r = 0, c = 0; l < n; ++l) { while (r < n && c < L) { ++r; c += max(cntw[r][i] - l, 0); } if (c >= L) { lth[l][r] = min(lth[l][r], i); } else break; c -= max(cnth[l][i] - (n - r), 0); } } for (int d = 1; d <= n; ++d) { for (int i = 0; i + d <= n; ++i) { lth[i][i + d] = min(lth[i][i + d], min(lth[i + 1][i + d], lth[i][i + d - 1])); } } int q; cin >> q; for (int _ = 0; _ < q; ++_) { int l, r; cin >> l >> r; --l; cout << lth[l][r] << '\n'; } return 0; }