krsu 3406 (not my code)

#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef long long ll;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    int m = 2 * n - 1;
    vector<int> a(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i];
    }

    auto check = [&](int x) {
        vector<int> b(m);
        for (int i = 0; i < m; i++) {
            b[i] = (a[i] > x);
        }

        int l = 0, r = m - 1;
        for (int i = 1; i < n; i++) {
            if (b[i - 1] == b[i])
                l = i;
        }

        for (int i = m - 1; i >= n; i--) {
            if (b[i] == b[i - 1])
                r = i - 1;
        }

        if (n - 1 - l <= r - n + 1) {
            return (b[l] == 0);
        } else {
            return (b[r] == 0);
        }
    };

    int l = 1, r = m;
    while (l < r) {
        int m = (l + r) >> 1;
        if (check(m))
            r = m;
        else
            l = m + 1;
    }

    cout << l << "\n";
}

/*

4
3 5 1 4 2 7 6

*/