#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
const int dx[4]={ 1,0,-1,0 };
const int dy[4]={ 0,1,0,-1 };

template<typename T>
struct TreapSet{
private:
    struct Node{
        T x; // value
        int p; // priority
        Node* par; // parent
        Node* chi[2]; // children
        int s; // size of subtree
        T m; // minimum value of subtree
        int c; // counter
        Node(T _x, std::mt19937& mt){
            x = _x;
            p = mt();
            par = NULL;
            chi[0] = NULL;
            chi[1] = NULL;
            s = 1;
            m = _x;
            c = 1;
        }
        bool operator==(const Node& u){
            return x == u.x;
        }
        bool operator<(const Node& u){
            return x < u.x;
        }
    };

    int N;
    Node* root;
    std::mt19937 mt;

    Node* find(T _x){
        Node* u = root;
        while(u != NULL && u->x != _x){
            if(u->x > _x) u = u->chi[0];
            else u = u->chi[1];
        }
        return u;
    }
    void update(Node* u){
        u->s = (u->chi[0] != NULL ? u->chi[0]->s : 0) + (u->chi[1] != NULL ? u->chi[1]->s : 0) + 1;
        u->m = u->x;
        if(u->chi[0] != NULL && u->chi[0]->m < u->m) u->m = u->chi[0]->m;
        if(u->chi[1] != NULL && u->chi[1]->m < u->m) u->m = u->chi[1]->m;
    }
    void rotateRight(Node* u){
        Node* p = u->par;
        u->par = p->par;
        if(p->par != NULL){
            if(p->par->chi[0] == p) p->par->chi[0] = u;
            else p->par->chi[1] = u;
        }
        p->par = u;
        p->chi[0] = u->chi[1];
        if(u->chi[1] != NULL) u->chi[1]->par = p;
        u->chi[1] = p;
        update(p);
        update(u);
    }
    void rotateLeft(Node* u){
        Node* p = u->par;
        u->par = p->par;
        if(p->par != NULL){
            if(p->par->chi[0] == p) p->par->chi[0] = u;
            else p->par->chi[1] = u;
        }
        p->par = u;
        p->chi[1] = u->chi[0];
        if(u->chi[0] != NULL) u->chi[0]->par = p;
        u->chi[0] = p;
        update(p);
        update(u);
    }
    void bubbleUp(Node* u){
        while(u->par != NULL && u->par->p > u->p){
            if(u->par->chi[0] == u) rotateRight(u);
            else rotateLeft(u);
        }
        if(u->par == NULL) root = u;
    }
    void dfsPrint(Node* u, int t){
        if(u == NULL) return;
        std::cout << u->x;
        if(t == 1) std::cout << "(" << u->s << ")";
        std::cout << " ";
        dfsPrint(u->chi[0], t);
        std::cout << u->x << " ";
        dfsPrint(u->chi[1], t);
        std::cout << u->x << " ";
    }
public:
    TreapSet(){
        N = 0;
        root = NULL;
        std::random_device rnd;
        std::mt19937 mt2(rnd());
        mt = mt2;
    }
    void add(T _x){
        int c = count(_x);
        if(c > 0) return;
        //if(c > 0) { find(_x)->c++; return; }
        Node* u = new Node(_x, mt);
        if(N == 0){
            root = u;
        }
        else{
            Node* p = root;
            Node* v = root;
            while(v != NULL){
                p = v;
                p->s++;
                if(p->m > _x) p->m = _x;
                if(v->x > _x) v = v->chi[0];
                else v = v->chi[1];
            }
            if(p->x > _x){
                p->chi[0] = u;
                u->par = p;
            }
            else{
                p->chi[1] = u;
                u->par = p;
            }
            bubbleUp(u);
        }
        N++;
    }
    void erase(T _x){
        int c = count(_x);
        if(c == 0) return;
        //if(c > 1){ find(_x)->c--; return; }
        if(N == 1){
            delete root;
            root = NULL;
        }
        else{
            Node* u = find(_x);
            while(u->chi[0] != NULL || u->chi[1] != NULL){
                if(u->chi[0] == NULL){
                    rotateLeft(u->chi[1]);
                }
                else if(u->chi[1] == NULL){
                    rotateRight(u->chi[0]);
                }
                else if(u->chi[0]->p > u->chi[1]->p){
                    rotateLeft(u->chi[1]);
                }
                else{
                    rotateRight(u->chi[0]);
                }
                if(u == root) root = u->par;
            }
            if(u->par->chi[0] == u) u->par->chi[0] = NULL;
            else u->par->chi[1] = NULL;
            Node* v = u->par;
            delete u;
            while(v != NULL){
                update(v);
                v = v->par;
            }
        }
        N--;
    }
    int count(T _x){
        Node* u = find(_x);
        if(u == NULL) return 0;
        else return u->c;
    }
    int size(){
        return N;
    }
    T& operator [](int i){
        assert(0 <= i && i < N);
        int n = 0;
        Node* u = root;
        while(u->chi[0] != NULL || u->chi[1] != NULL){
            int j = n + (u->chi[0] != NULL ? u->chi[0]->s : 0);
            if(i == j) break;
            if(i < j) u = u->chi[0];
            else{
                n += (u->chi[0] != NULL ? u->chi[0]->s : 0) + 1;
                u = u->chi[1];
            }
        }
        return u->x;
    }
    int lower_bound(T _x){
        Node* u = root;
        bool seted = false;
        T ret;
        while(u != NULL){
            if(u->x >= _x && (!seted || u->x < ret)){
                ret = u->x;
                seted = true;
            }
            if(u->chi[0] == NULL) u = u->chi[1];
            else if(u->chi[1] == NULL) u = u->chi[0];
            else if(u->chi[1]->m <= _x) u = u->chi[1];
            else{
                if(!seted || ret > u->chi[1]->m){
                    ret = u->chi[1]->m;
                    seted = true;
                }
                u = u->chi[0];
            }
        }
        if(!seted) return N;
        return index(ret);
    }
    int index(T _x){
        Node* u = root;
        int ret = 0;
        while(u != NULL && u->x != _x){
            if(u->x > _x) u = u->chi[0];
            else{
                ret += (u->chi[0] != NULL ? u->chi[0]->s : 0) + 1;
                u = u->chi[1];
            }
        }
        if(u == NULL) return -1;
        if(u->chi[0] != NULL) ret += u->chi[0]->s;
        return ret;
    }
    void print(int t=0){
        Node* u = root;
        dfsPrint(u, t);
        std::cout << std::endl;
    }
};

int N;
int a[100000];

ll count(int m){
    TreapSet<pair<int,int>> st;
    ll ret = 0;
    int sum = 0;
    for(int r=0; r<N; r++){
        st.add({ -sum,r });
        if(a[r] < m) sum++;
        else sum--;
        ret += r+1-st.lower_bound({ 1-sum,-1 });
    }
    return ret;
}

signed main(){
    cin >> N;
    rep(i, N) cin >> a[i];

    int l = 1;
    int r = 1e9+1;
    while(r-l > 1){
        int m = (l+r)/2;
        if(count(m) < (ll)N*(N+1)/2/2+1) l = m;
        else r = m;
    }
    cout << l << endl;
}

Measured memory_bytes: 191504