【題解】Codeforces 1291C. Mind Control

#include <iostream>
#include <deque>
using namespace std;
#define pii pair<int, int>
 
const int maxn = 3505;
int t, n, m, k, w, a[maxn], b[maxn], ans, l, r, dl, dr;
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while (t--){
        cin >> n >> m >> k;
        for (int i = 0; i < n; i++){
            cin >> a[i];
        }
        w = n-m;
        for (int i = 0; i+w < n; i++){
            b[i] = max(a[i], a[i+w]);
        }
        if (k >= m-1){
            ans = 0;
            for (int i = 0; i < m; i++){
                if (b[i] > ans) ans = b[i];
            }
            cout << ans << "\n";
        }
        else {
            deque <pii> dq;
            ans = 0;
            w = m-k-1;
            for (int i = 0; i < m; i++){
                while (!dq.empty() && b[i] < dq.back().second){
                    dq.pop_back();
                }
                while (!dq.empty() && dq.front().first < i-w){
                    dq.pop_front();
                }
                dq.push_back({i, b[i]});
                if (i >= w) ans = max(ans, dq.front().second);
            }
            cout << ans << "\n";
        }
    }
}