//code by lynmisakura.wish to be accepted!
/****************************/
#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<bitset>
#include <climits>
#include<set>
#include<bitset>
using namespace std;
/***************************/
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef pair<int, int> pi;
typedef vector<pair<int, int>> vpi;
 
//const long long INF = 1LL << 55;
 
#define itn int
#define endl '\n'
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ss second
#define ff first
#define dup(x,y) ((x) + (y) - 1)/(y)
#define mins(x,y) x = min(x,y)
#define maxs(x,y) x = max(x,y)
#define all(x) (x).begin(),(x).end()
#define Rep(n) for(int i = 0;i < n;i++)
#define rep(i,n) for(int i = 0;i < n;i++)
#define rrep(i,n) for(int i = n - 1;i >= 0;i--)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
#define ioboost cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20)

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll qp(ll a, ll b) { ll ans = 1; do { if (b & 1)ans = 1ll * ans*a; a = 1ll * a*a; } while (b >>= 1); return ans; }
ll qp(ll a, ll b, int mo) { ll ans = 1; do { if (b & 1)ans = 1ll * ans*a%mo; a = 1ll * a*a%mo; } while (b >>= 1); return ans; }
 
#define _GLIBCXX_DEBUG
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

#define MAX_N 400010
class BIT_for_inversion {
	// Implementation of a Binary Indexed Tree (Fennwick Tree)
public:
	/*BIT(std::vector<int> list) {
		// Initialize BIT with list in O(n*log(n))
		m_array = std::vector<int>(list.size() + 1, 0);
		for (int idx = 0; idx < list.size(); idx++) {
			update(idx, list[idx]);
		}
	}*/

	BIT_for_inversion(std::vector<int> list) {
		// Initialize BIT with list in O(n)
      array_for_inversion = vector<int>(MAX_N,0);
      default_array = vector<int> (list.size(),0);
		for (int idx = 0; idx < list.size(); idx++) {
			default_array[idx] = list[idx];
		}
	}

	int prefix_query(int idx) const {
		// Computes prefix sum of up to the element at index idx
		int result = 0;
		for (++idx; idx > 0; idx -= idx & -idx) {
			result += array_for_inversion[idx];
		}
		return result;
	}

	int range_query(int from_idx, int to_idx) const {
		// Computes the range sum between two indices (both inclusive)
        if (from_idx == 0)
            return prefix_query(to_idx);
        else
            return prefix_query(to_idx) - prefix_query(from_idx - 1);
	}

	void update(int idx, int add) {
		// Add a value to the element at index idx
		for (++idx; idx < MAX_N; idx += idx & -idx) {
			array_for_inversion[idx] += add;
		}
	}
   long long inversion(){
      long long ans = 0;
      for(int j = 0;j < default_array.size();j++){
         ans += (long long)((j) - prefix_query(default_array[j]));
         update(default_array[j],1);
      }
      return ans;
   }
private:
   vector<int> array_for_inversion;
   vector<int> default_array;
};

ll n;
vector<int> a,sorted_a;
ll half,tot;

bool judge(int mid){
   vector<int> b(n),c(n+1,0);
   rep(i,n){
      if(a[i] >= mid)b[i] = 1;else b[i] = -1;
   }
   rep(i,n)c[i+1] = c[i] + b[i];
  
   int min_c = -1;
   rep(i,n+1)mins(min_c,c[i]);
   rep(i,n+1)c[i] -= min_c;
   
   // cout << "mid : " << mid << endl;
   // for(auto i : c)cout << i << " ";
   // cout << endl;
   
   BIT_for_inversion bit(c);
   //cout << "tot - bit.inversion() = " << tot - bit.inversion() << endl; 
   ll cnt = tot - bit.inversion();
   return cnt >= half;
}

int main(void){
   ioboost;
   cin >> n; 
   tot = n*(n+1)/2;
   half = (tot + 1)/2;
   // cout << "tot : " << tot << endl;
   // cout << "half : " << half << endl;
   
   rep(i,n){
      int x;cin >> x;
      a.pb(x);
      sorted_a.pb(x);
   }
   sort(all(sorted_a));
   UNIQUE(sorted_a);
   int sz = sorted_a.size();
   int l = 0,r = sz;
   while(r - l > 1){
      int mid = (l+r)/2;
      // cout << sorted_a[mid] << endl;
      if(judge(sorted_a[mid])){
         // cout << "true" << endl;
         l = mid;
      }else{
         // cout << "false" << endl;
         r = mid;
      }
   }

   cout << sorted_a[l] << endl;
   return 0;
}

Measured memory_bytes: 4340