func_code_string: #include <bits/stdc++.h>   using namespace std;   int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);     int n, sg, m, k;     cin >> n >> sg >> m >> k;     vector<int> a(n), starts(n, n);     for (int i = 0; i < n; i++) {       cin >> a[i];     }     for (int i = 0; i < sg; i++) {       int l, r;       cin >> l >> r;       l--;       r--;       starts[r] = min(starts[r], l);     }     auto bldPrefCnt = [&](int x) {       vector<int> res(n);       int cur = 0;       for (int i = 0; i < n; i++) {         if (a[i] <= x) {           cur++;         }         res[i] = cur;       }       return res;     };     auto check = [&](int x) {       auto prefs = bldPrefCnt(x);       vector<int> sufMem(n, -1);       map<int, int> sufL;       for (int i = 0; i < n; i++) {         int l = starts[i];         if (l == n) {           continue;         }         auto itL = sufL.lower_bound(l);         if (itL != sufL.end()) {           sufMem[i] = itL->first;         }         while (sufL.size() > 0 && l <= sufL.rbegin()->second) {           sufL.erase(prev(sufL.end()));         }         sufL[i] = l;       }       vector<vector<int>> dp(n, vector<int>(m + 1, 0));       int best = 0;       vector<int> prefMx(n);       for (int j = 1; j <= m; j++) {         vector<int> nxtPrefMx(n);         for (int i = 0; i < n; i++) {           auto &cur = dp[i][j];           if (starts[i] < n) {             int l = starts[i];             if (l > 0) {               cur = (prefs[i] - prefs[l - 1]) + prefMx[l - 1];             } else {               cur = prefs[i];             }             int u = sufMem[i];             if (u != -1) {               int take = prefs[i] - prefs[u];               cur = max(cur, take + dp[u][j - 1]);             }           }           nxtPrefMx[i] =               (i > 0 && nxtPrefMx[i - 1] > cur) ? nxtPrefMx[i - 1] : cur;           best = max(best, cur);         }         prefMx = nxtPrefMx;       }       return best >= k;     };     int l = 0, r = 1e9 + 10;     int ans = -1;     if (check(r)) {       while (l < r) {         int mid = (l + r) / 2;         if (check(mid)) {           r = mid;         } else {           l = mid + 1;         }       }       ans = r;     }     cout << ans << endl;   }   