Language: C++

#include <functional>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

template<typename Monoid>
struct SegmentTree {
    using F = function<Monoid(Monoid, Monoid)>;

    int sz;
    vector<Monoid> seg;

    const F f;
    const Monoid M1;

    SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
        sz = 1;
        while(sz < n) sz <<= 1;
        seg.assign(2 * sz, M1);
    }

    void set(int k, const Monoid &x) {
        seg[k + sz] = x;
    }

    void build() {
        for(int k = sz - 1; k > 0; k--) {
            seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
        }
    }

    void update(int k, const Monoid &x) {
        k += sz;
        seg[k] = x;
        while(k >>= 1) {
            seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
        }
    }

    Monoid query(int a, int b) {
        Monoid L = M1, R = M1;
        for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
            if(a & 1) L = f(L, seg[a++]);
            if(b & 1) R = f(seg[--b], R);
        }
        return f(L, R);
    }

    Monoid operator[](const int &k) const {
        return seg[k + sz];
    }
};

int main()
{
    int n;
    cin >> n;
    int a[100002];
    for(int i = 0; i < n; i++) cin >> a[i];
    int now = 1048576 * 512 - 1;
    int mid = 1048576 * 256;
    while(mid){
        int b[100002]{0};
        for(int i = 0; i < n; i++){
            if(a[i] >= now) b[i]++;
            else b[i]--;
            b[i + 1] += b[i];
        }
        ll s[200002]{0};
        for(int i = 0; i < n; i++) s[b[i] + 100000]++;
        SegmentTree<ll> seg(200000, [](ll a, ll b){return ll a + b;}, 0ll);
        for(int i = 0; i <= 200000; i++) seg.set(i, s[i]);
        seg.build();
        int k = 0;
        ll sum = 0;
        for(int i = 0; i < n; i++){
            sum += seg.query(k + 100000, 200001);
            seg.update(b[i] + 100000, seg[b[i] + 100000] - 1);
            if(a[i] < now) k--;
            else k++;
        }
        if(sum >= (n * (n + 1) / 2 + 1) / 2) now += mid;
        else now -= mid;
        mid /= 2;
    }
    int b[100002]{0};
    for(int i = 0; i < n; i++){
        if(a[i] >= now) b[i]++;
        else b[i]--;
        b[i + 1] += b[i];
    }
    ll s[200002]{0};
    for(int i = 0; i < n; i++) s[b[i] + 100000]++;
    SegmentTree<ll> seg(200000, [](ll a, ll b){return ll a + b;}, 0ll);
    for(int i = 0; i <= 200000; i++) seg.set(i, s[i]);
    seg.build();
    int k = 0;
    ll sum = 0;
    for(int i = 0; i < n; i++){
        sum += seg.query(k + 100000, 200001);
        seg.update(b[i] + 100000, seg[b[i] + 100000] - 1);
        if(a[i] < now) k--;
        else k++;
    }
    if(sum < (n * (n + 1) / 2 + 1) / 2) now--;
    cout << now << endl;
}

Compiler output:
a.cc: In lambda function:
a.cc:72:62: error: expected primary-expression before 'a'
   72 |         SegmentTree<ll> seg(200000, [](ll a, ll b){return ll a + b;}, 0ll);
      |                                                              ^
a.cc:72:61: error: expected ';' before 'a'
   72 |         SegmentTree<ll> seg(200000, [](ll a, ll b){return ll a + b;}, 0ll);
      |                                                             ^~
      |                                                             ;
a.cc: In function 'int main()':
a.cc:72:74: error: no matching function for call to 'SegmentTree<long long int>::SegmentTree(int, main()::<lambda(ll, ll)>, long long int)'
   72 |         SegmentTree<ll> seg(200000, [](ll a, ll b){return ll a + b;}, 0ll);
      |                                                                          ^
a.cc:17:5: note: candidate: 'SegmentTree<Monoid>::SegmentTree(int, F, const Monoid&) [with Monoid = long long int; F = std::function<long long int(long long int, long long int)>]'
   17 |     SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
      |     ^~~~~~~~~~~
a.cc:17:32: note:   no known conversion for argument 2 from 'main()::<lambda(ll, ll)>' to 'SegmentTree<long long int>::F' {aka 'std::function<long long int(long long int, long long int)>'}
   17 |     SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
      |                        ~~~~~~~~^
a.cc:8:8: note: candidate: 'SegmentTree<long long int>::SegmentTree(const SegmentTree<long long int>&)'
    8 | struct SegmentTree {
      |        ^~~~~~~~~~~
a.cc:8:8: note:   candidate expects 1 argument, 3 provided
a.cc:8:8: note: candidate: 'SegmentTree<long long int>::SegmentTree(SegmentTree<long long int>&&)'
a.cc:8:8: note:   candidate expects 1 argument, 3 provided
a.cc: In lambda function:
a.cc:95:58: error: expected primary-expression before 'a'
   95 |     SegmentTree<ll> seg(200000, [](ll a, ll b){return ll a + b;}, 0ll);
      |                                                          ^
a.cc:95:57: error: expected ';' before 'a'
   95 |     SegmentTree<ll> seg(200000, [](ll a, ll b){return ll a + b;}, 0ll);
      |                                                         ^~
      |                                                         ;
a.cc: In function 'int main()':
a.cc:95:70: error: no matching function for call to 'SegmentTree<long long int>::SegmentTree(int, main()::<lambda(ll, ll)>, long long int)'
   95 |     SegmentTree<ll> seg(200000, [](ll a, ll b){return ll a + b;}, 0ll);
      |                                                                      ^
a.cc:17:5: note: candidate: 'SegmentTree<Monoid>::SegmentTree(int, F, const Monoid&) [with Monoid = long long int; F = std::function<long long int(long long int, long long int)>]'
   17 |     SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
      |     ^~~~~~~~~~~
a.cc:17:32: note:   no known conversion for argument 2 from 'main()::<lambda(ll, ll)>' to 'SegmentTree<long long int>::F' {aka 'std::function<long long int(long long int, long long int)>'}
   17 |     SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
      |                        ~~~~~~~~^
a.cc:8:8: note: candidate: 'SegmentTree<long long int>::SegmentTree(const SegmentTree<long long int>&)'
    8 | struct SegmentTree {
      |        ^~~~~~~~~~~
a.cc:8:8: note:   candidate expects 1 argument, 3 provided
a.cc:8:8: note: candidate: 'SegmentTree<long long int>::SegmentTree(SegmentTree<long long int>&&)'
a.cc:8:8: note:   candidate expects 1 argument, 3 provided