Language: C++

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

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

template<typename T>
class SegmentTree {
private:
    int N;
    vector<T> v;
    vector<tuple<int, int, T>> heap;
    function<T(T, T)> merge;

    T init(int l, int r, int i) {
        if(l == r) {
            return 0;
        }
        if(r - l == 1) {
            T value = v[l];
            heap[i] = tie(l, r, value);
            return value;
        }
        T value = merge(init(l, (l + r)/2, i*2), init((l + r)/2, r, i*2 + 1));
        heap[i] = tie(l, r, value);
        return value;
    }

public:
    SegmentTree() {}

    SegmentTree(vector<T> s, function<T(T, T)> f) {
        merge = f;
        int n = s.size();
        for(N = 1;N < n;N *= 2);
        heap.resize(2*N, make_tuple(0, 0, 0));
        v.resize(N, 0);
        copy(s.begin(), s.end(), v.begin());
        init(0, N, 1);
    }

    SegmentTree(vector<T> s) : SegmentTree(s, [](T x, T y){return x + y;}) {}

    void update(int index, T value) {
        int l = 0;
        int r = N;
        int i = 1;
        for(;1 < r - l;) {
            int mid = (l + r)/2;
            if(index < mid) {
                r = mid;
                i *= 2;
            }else{
                l = mid;
                i = i*2 + 1;
            }
        }
        heap[i] = tie(l, r, value);

        for(i /= 2;0 < i;i /= 2) {
            int l, r;
            T lv, rv, v;
            tie(l, r) = heap[i];
            tie(ignore, ignore, lv) = heap[i*2];
            tie(ignore, ignore, rv) = heap[i*2 + 1];
            v = merge(lv, rv);
            heap[i] = tie(l, r, v);
        }
    }

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

        if(l == r) {
            return 0;
        }
        if(left == right) {
            return 0;
        }
        if(left == l && right == r) {
            return value;
        }
        if(r < mid) {
            return segment(l, r, i*2);
        }
        if(mid < l) {
            return segment(l, r, i*2 + 1);
        }
        return merge(segment(l, mid, i*2), segment(mid, r, i*2 + 1));
    }
};

bool check(int 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);
    SegmentTree<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 'void SegmentTree<T>::update(int, T) [with T = long long int]':
a.cc:114:19:   required from here
  114 |         seg.update(j, y + 1);
      |         ~~~~~~~~~~^~~~~~~~~~
a.cc:65:23: error: no match for 'operator=' (operand types are 'std::tuple<int&, int&>' and '__gnu_cxx::__alloc_traits<std::allocator<std::tuple<int, int, long long int> >, std::tuple<int, int, long long int> >::value_type' {aka 'std::tuple<int, int, long long int>'})
   65 |             tie(l, r) = heap[i];
      |             ~~~~~~~~~~^~~~~~~
In file included from /usr/include/c++/14/bits/memory_resource.h:47,
                 from /usr/include/c++/14/string:68,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52,
                 from a.cc:1:
/usr/include/c++/14/tuple:2355:9: note: candidate: 'template<class _U1, class _U2> std::__enable_if_t<((bool)__assignable<const _U1&, const _U2&>()), std::tuple<_T1, _T2>&> std::tuple<_T1, _T2>::operator=(const std::tuple<_U1, _U2>&) [with _U2 = _U1; _T1 = int&; _T2 = int&]'
 2355 |         operator=(const tuple<_U1, _U2>& __in)
      |         ^~~~~~~~
/usr/include/c++/14/tuple:2355:9: note:   template argument deduction/substitution failed:
a.cc:65:23: note:   candidate expects 2 arguments, 3 provided
   65 |             tie(l, r) = heap[i];
      |             ~~~~~~~~~~^~~~~~~
/usr/include/c++/14/tuple:2365:9: note: candidate: 'template<class _U1, class _U2> std::__enable_if_t<((bool)__assignable<_U1, _U2>()), std::tuple<_T1, _T2>&> std::tuple<_T1, _T2>::operator=(std::tuple<_U1, _U2>&&) [with _U2 = _U1; _T1 = int&; _T2 = int&]'
 2365 |         operator=(tuple<_U1, _U2>&& __in)
      |         ^~~~~~~~
/usr/include/c++/14/tuple:2365:9: note:   template argument deduction/substitution failed:
a.cc:65:23: note:   candidate expects 2 arguments, 3 provided
   65 |             tie(l, r) = heap[i];
      |             ~~~~~~~~~~^~~~~~~
/usr/include/c++/14/tuple:2375:9: note: candidate: 'template<class _U1, class _U2> std::__enable_if_t<((bool)__assignable<const _U1&, const _U2&>()), std::tuple<_T1, _T2>&> std::tuple<_T1, _T2>::operator=(const std::pair<_U1, _U2>&) [with _U2 = _U1; _T1 = int&; _T2 = int&]'
 2375 |         operator=(const pair<_U1, _U2>& __in)
      |         ^~~~~~~~
/usr/include/c++/14/tuple:2375:9: note:   template argument deduction/substitution failed:
a.cc:65:23: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::tuple<int, int, long long int> >, std::tuple<int, int, long long int> >::value_type' {aka 'std::tuple<int, int, long long int>'} is not derived from 'const std::pair<_T1, _T2>'
   65 |             tie(l, r) = heap[i];
      |             ~~~~~~~~~~^~~~~~~
/usr/include/c++/14/tuple:2386:9: note: candidate: 'template<class _U1, class _U2> std::__enable_if_t<((bool)__assignable<_U1, _U2>()), std::tuple<_T1, _T2>&> std::tuple<_T1, _T2>::operator=(std::pair<_U1, _U2>&&) [with _U2 = _U1; _T1 = int&; _T2 = int&]'
 2386 |         operator=(pair<_U1, _U2>&& __in)
      |         ^~~~~~~~
/usr/include/c++/14/tuple:2386:9: note:   template argument deduction/substitution failed:
a.cc:65:23: note:   '__gnu_cxx::__alloc_traits<std::allocator<std::tuple<int, int, long long int> >, std::tuple<int, int, long long int> >::value_type' {aka 'std::tuple<int, int, long long int>'} is not derived from 'std::pair<_T1, _T2>'
   65 |             tie(l, r) = heap[i];
      |             ~~~~~~~~~~^~~~~~~
/usr/include/c++/14/tuple:2332:7: note: candidate: 'std::tuple<_T1, _T2>& std::tuple<_T1, _T2>::operator=(std::__conditional_t<((bool)__assignable<const _T1&, const _T2&>()), const std::tuple<_T1, _T2>&, const std::__nonesuch&>) [with _T1 = int&; _T2 = int&; std::__conditional_t<((bool)__assignable<const _T1&, const _T2&>()), const std::tuple<_T1, _T2>&, const std::__nonesuch&> = const std::tuple<int&, int&>&]'
 2332 |       operator=(__conditional_t<__assignable<const _T1&, const _T2&>(),
      |       ^~~~~~~~
/usr/include/c++/14/tuple:2334:52: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<std::tuple<int, int, long long int> >, std::tuple<int, int, long long int> >::value_type' {aka 'std::tuple<int, int, long long int>'} to 'std::__conditional_t<true, const std::tuple<int&, int&>&, const std::__nonesuch&>' {aka 'const std::tuple<int&, int&>&'}
 2332 |       operator=(__conditional_t<__assignable<const _T1&, const _T2&>(),
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 2333 |                                 const tuple&,
      |                                 ~~~~~~~~~~~~~       
 2334 |                                 const __nonesuch&> __in)
      |                                 ~~~~~~~~~~~~~~~~~~~^~~~
/usr/include/c++/14/tuple:2343:7: note: candidate: 'std::tuple<_T1, _T2>& std::tuple<_T1, _T2>::operator=(std::__conditional_t<((bool)__assignable<_T1, _T2>()), std::tuple<_T1, _T2>&&, std::__nonesuch&&>) [with _T1 = int&; _T2 = int&; std::__conditional_t<((bool)__assignable<_T1, _T2>()), std::tuple<_T1, _T2>&&, std::__nonesuch&&> = std::tuple<int&, int&>&&]'
 2343 |       operator=(__conditional_t<__assignable<_T1, _T2>(),
      |       ^~~~~~~~
/usr/include/c++/14/tuple:2345:47: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<std::tuple<int, int, long long int> >, std::tuple<int, int, long long int> >::value_type' {aka 'std::tuple<int, int, long long int>'} to 'std::__conditional_t<true, std::tuple<int&, int&>&&, std::__nonesuch&&>' {aka 'std::tuple<int&, int&>&&'}
 2343 |       operator=(__conditional_t<__assignable<_T1, _T2>(),
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 2344 |                                 tuple&&,
      |                                 ~~~~~~~~       
 2345 |                                 __nonesuch&&> __in)
      |                                 ~~~~~~~~~~~~~~^~~~