#include <bits/stdc++.h>
 
 
#define pb push_back
#define nl puts ("")
#define sp printf ( " " )
#define phl printf ( "hello\n" )
#define ff first
#define ss second
#define POPCOUNT __builtin_popcountll
#define RIGHTMOST __builtin_ctzll
#define LEFTMOST(x) (63-__builtin_clzll((x)))
#define MP make_pair
#define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
#define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
#define CLR(x,y) memset(x,y,sizeof(x))
#define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
#define SQ(x) ((x)*(x))
#define ABS(x) ((x)<0?-(x):(x))
#define FABS(x) ((x)+eps<0?-(x):(x))
#define ALL(x) (x).begin(),(x).end()
#define LCM(x,y) (((x)/gcd((x),(y)))*(y))
#define SZ(x) ((vlong)(x).size())
#define NORM(x) if(x>=mod) x-=mod;if(x<0) x+=mod;
#define MOD(x,y) (((x)*(y))%mod)
#define ODD(x) (((x)&1)==0?(0):(1))
#define Set(N,cur) N=(N|(1LL<<cur))
#define Reset(N,cur) N=(N&(~(1LL<<cur)))
#define Check(N,cur) (!((N&(1LL<<cur))==0))
#define fast_cin ios_base::sync_with_stdio(false);cin.tie(NULL)
#define dump(x) cerr<<"~ "<<#x<<" = "<<x<<endl
//Imran addition
#define rep(i,n) for(int i = 1; i <= n; i++)
#define mem CLR
#define pf printf
#define sc scanf
#define endl "\n"
#define gi(k) scanf("%d",&k)
#define gl(k) scanf("%lld",&k)
#define NMAX 2147483647
#define LMAX 9223372036854775807LL
 
using namespace std;
 
 
#define LL long long
#define LLU long long unsigned int
typedef long long vlong;
typedef unsigned long long uvlong;
typedef pair < int, int > pii;
typedef pair < vlong, vlong > pll;
typedef vector<int> vi;
typedef vector<vlong> vl;
typedef vector<pll> vll;
 
inline vlong gcd ( vlong a, vlong b ) {
    a = ABS ( a ); b = ABS ( b );
    while ( b ) { a = a % b; swap ( a, b ); } return a;
}
 
 
const vlong inf = 2147383647;
const vlong mod = 1000000007;
const double pi = 2 * acos ( 0.0 );
const double eps = 1e-9;


/// Treap which support multiple entry, works like a multiset
/// If you want to use like a set then just erase the element before insert
/// All the functions are similar to the built in treap
/// Every function works in log(N) except unite()

struct node{
    int key, prior, size;
    struct node *l, *r;
    node() { }
    node(int v) {
        key = v;
        prior = rand();
        size = 1;
        l = r = NULL;
    }
    node (int key, int prior) : key(key), prior(prior), l(NULL), r(NULL) { }
};

typedef node* pnode;

struct Treap{
    pnode t;
    Treap(){}

    /// Returns size of treap
    int size(){
        return sz(t);
    }

    int sz(pnode t){
        return t ? t->size:0;
    }

    void upd_sz(pnode t){
        if(t) t->size = sz(t->l) + 1 + sz(t->r);
    }

    /// Split t into l and r such that all elements in l
    /// is less than key and all elements in r is greater than key
    void split(pnode t, pnode &l, pnode &r, int key){
        if(!t) l = r = NULL;
        else if(t->key < key) split(t->r, t->r, r, key), l = t;
        else split(t->l, l, t->l, key), r = t;
        upd_sz(t);
    }



    void insert(pnode &t, pnode it){
        if(!t) t = it;
        else if(it->prior > t->prior) split(t, it->l, it->r, it->key), t = it;
        else insert(t->key < it->key ? t->r:t->l, it);
        upd_sz(t);
    }

    int orderOf(pnode temp, int k){
        int x = 0;
        if(temp == NULL) return 0;
        if(temp->key < k) return sz(temp->l) + 1 + orderOf(temp->r, k);
        else return orderOf(temp->l, k);
    }

    void nullify(pnode t){
        if(t == NULL) return;
        nullify(t->l); nullify(t->r);
        delete t;
        t->l = NULL; t->r = NULL; t = NULL;
        free(t);
    }

    /// Insert k in the treap
    void insert(int k){
        pnode it = new node(k);
        insert(t, it);
    }


    /// Returns number of elements less than k
    int order_of_key(int k){
        return orderOf(t, k);
    }

    /// Clear the treap
    void clear(){
        nullify(t);
        t = NULL;
    }

}treap;

#define N 100005
int ar[N],br[N],n;

int f(int x) {

    rep(i,n) {
        if(ar[i] < x) br[i] = -1;
        else br[i] = 1;
    }

    treap.clear();
    treap.insert(0);
    //treap.insert(-10); dump(treap.order_of_key(-12));

    int tmp = 0;
    vlong sum = 0,tot,half;

    tot = n; tot *= n+1; tot /= 2;
    half = (tot+1)/2;

    rep(i,n) {
        tmp += br[i];
        sum += treap.order_of_key(tmp+1);
        treap.insert(tmp);
    }

    //dump(sum);

    return (sum >= half);
}

 
int main () {
 
 	#ifdef forthright48
    freopen ( "00_input.txt", "r", stdin ); //freopen ( "00_output.txt", "w", stdout );
 	#endif
 
	int  ans = 0; 
    cin >> n;

    rep(i,n) {
        gi(ar[i]);
    }


    int low = 1, high = 1e9, md;

    while(low <= high) {
        md = (low+high)/2;

        if(f(md)) {
            ans = md;
            low = md+1;
        }

        else {
            high = md-1;
        }
    }

    cout << ans << endl;
	
 
    return 0;
}

Measured memory_bytes: 5760