Language: C++

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

#define LL long long
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()

template<typename T>
class LazySegmentTree {
private:
    int N;
    vector<pair<int, int>> domain;
    vector<T> values;
    vector<function<T(T)>> lazy;
    function<T(T, T)> merge;

    T init(int l, int r, int i, vector<T> s) {
        if(l == r) {
            return 0;
        }
        if(r - l == 1) {
            domain[i] = make_pair(l, r);
            values[i] = s[l];
            return values[i];
        }
        domain[i] = make_pair(l, r);
        values[i] = merge(init(l, (l + r)/2, i*2), init((l + r)/2, r, i*2 + 1));
        return values[i];
    }

    void eval() {
    }

    T dive(int l, int r, int i=1) {
        int left, right, mid;
        tie(left, right) = domain[i];
        mid = (left + right)/2;

        if(l == r) {
            return 0;
        }
        if(r - l == 1) {
            return values[i];
        }

        if(r < mid) {
            return dive(l, r, i*2);
        }
        if(mid < l) {
            return dive(l, r, i*2 + 1);
        }
        return merge(dive(l, mid, i*2), dive(mid, r, i*2 + 1));
    }
public:
    LazySegmentTree() {}
    LazySegmentTree(vector<T> s, function<T(T, T)> f) {
        merge = f;
        int n = s.size();
        for(N = 1;N < n;N *= 2);
        domain.resize(2*N);
        values.resize(2*N);
        s.resize(N, 0);
        init(0, N, 1, s);
    }
    LazySegmentTree(vector<T> s) : LazySegmentTree(s, [](T x, T y){return x + y;}) {}

    void update(int index, T value) {
        int i = index + N;
        values[i] = value;

        for(i /= 2;0 < i;i /= 2) {
            values[i] = merge(values[i*2], values[i*2 + 1]);
        }
    }

    T segment(int l, int r) {
        return dive(l + N, r + N);
    }

    void query(int l, int r, function<T(T)> f) {
    }
};

bool check(LL N, vector<LL> a, LL p) {
    vector<LL> t(a);
    REP(i, N) {
        t[i] = p <= a[i] ? 1 : -1;
    }
    vector<LL> s(N + 1, 0);
    REP(i, N) {
        s[i + 1] = s[i] + t[i];
    }
    vector<LL> v(2*N + 1, 0);
    LazySegmentTree<LL> seg(v);
    LL ans = 0;
    REP(i, N + 1) {
        LL j = s[i] + N;
        ans += seg.segment(0, j + 1);
        LL y = seg.segment(j, j + 1);
        seg.update(j, y + 1);
    }
    return (N + 1)*N/4 <= ans;
}

int main() {
    int N;
    cin >> N;
    vector<LL> a(N);
    REP(i, N) {
        cin >> a[i];
    }
    vector<LL> com(a);
    sort(ALL(com));

    int left = 0;
    int right = N - 1;
    if(check(N, a, com[right])) {
        cout << com[right] << endl;
        return 0;
    }

    for(;1 < right - left;) {
        int mid = (left + right)/2;
        bool c = check(N, a, com[mid]);
        if(c) {
            left = mid;
        }else{
            right = mid;
        }
    }
    cout << com[left] << endl;
    return 0;
}


Compiler output:
a.cc: In instantiation of 'T LazySegmentTree<T>::init(int, int, int, std::vector<_Tp>) [with T = long long int]':
a.cc:64:9:   required from 'LazySegmentTree<T>::LazySegmentTree(std::vector<_Tp>, std::function<T(T, T)>) [with T = long long int]'
   64 |         init(0, N, 1, s);
      |         ^~~~
a.cc:66:82:   required from 'LazySegmentTree<T>::LazySegmentTree(std::vector<_Tp>) [with T = long long int]'
   66 |     LazySegmentTree(vector<T> s) : LazySegmentTree(s, [](T x, T y){return x + y;}) {}
      |                                                                                  ^
a.cc:95:30:   required from here
   95 |     LazySegmentTree<LL> seg(v);
      |                              ^
a.cc:28:31: error: no matching function for call to 'LazySegmentTree<long long int>::init(int&, int, int)'
   28 |         values[i] = merge(init(l, (l + r)/2, i*2), init((l + r)/2, r, i*2 + 1));
      |                           ~~~~^~~~~~~~~~~~~~~~~~~
a.cc:18:7: note: candidate: 'T LazySegmentTree<T>::init(int, int, int, std::vector<_Tp>) [with T = long long int]'
   18 |     T init(int l, int r, int i, vector<T> s) {
      |       ^~~~
a.cc:18:7: note:   candidate expects 4 arguments, 3 provided
a.cc:28:56: error: no matching function for call to 'LazySegmentTree<long long int>::init(int, int&, int)'
   28 |         values[i] = merge(init(l, (l + r)/2, i*2), init((l + r)/2, r, i*2 + 1));
      |                                                    ~~~~^~~~~~~~~~~~~~~~~~~~~~~
a.cc:18:7: note: candidate: 'T LazySegmentTree<T>::init(int, int, int, std::vector<_Tp>) [with T = long long int]'
   18 |     T init(int l, int r, int i, vector<T> s) {
      |       ^~~~
a.cc:18:7: note:   candidate expects 4 arguments, 3 provided