#include <bits/stdc++.h>
        using namespace std;
     
     
    // Function that counts # of elements in m smaller than x   

          
    int64_t counter(int64_t N, int64_t x, vector<int64_t> A) {
          vector<int64_t>  C(N), D(N), H(2*N+1);
          
          for (int64_t i = 0; i < N; i++) {
            if(A.at(i) < x){
              C.at(i)= -1 ; 
            }
            else{
              C.at(i)= 1 ; 
            } 
          }
          
          int64_t sum = 0; 
          for (int64_t i=0; i < N ; i++ ){
          sum = sum + C.at(i);  
          H.at( N + sum )++ ;  
          } 
          
          int64_t S= 0; 
          for (int64_t i = N ; i < 2*N+1; i++) {
            S = S + H.at(i);  
          }   
          
     
          int64_t T=0;  // total number that is larger than or equals to x
          int64_t U=0;  // U current level 
          
          // main subroutine
          for(int64_t j=0; j < N; j++ ){
            
    //        for(int k=0; k< 2*N+1 ; k++){
    //         cout<< H.at(k) ; 
    //        }
            
            T = T + S;
            // cout << S << endl; 
            // update S and Histogram
            
            if(C.at(j)==1){
              S =  S- H.at( N + U ) - 1   ;
              H.at(N+U+1) -- ;
              U = U+1; 
            }
            else{
              S=  S + H.at( N+ U-1) - 1 ; 
              H.at(N+U-1) -- ; 
              U= U-1; 
            }
          } 
        return N*(N+1)/2 - T; 
    }      
         
        int main() {
          int64_t N ; // the number of elements 
          cin >> N ;
          vector<int64_t> A(N), B(N);  

          
             // A is the sequence given by the problem
             // B will be a sorted copy 
             // C[i] will indicate x is larger A[i] than or not; 
             // D[i] will be accumulated version of C[i]
             // H[i] will be histogram
             // H[i+N] indicates the number of times i has appeared  
          
        for (int i = 0; i < N; i++) {
            cin >> A.at(i);
            B.at(i) = A.at(i);  
          }

// for test          
//          for(int64_t i=0; i<N; i++){
//            A.at(i)=i+1; 
//            B.at(i) = A.at(i);  
//          }
          
          sort(B.begin(), B.end());
          
          int64_t  threshold = N*(N+1)/4; 
          
          int64_t i=0;
          int64_t j=N-1; 
          int64_t k=0;
          
          if ( counter( N, B.at(j), A)  <= threshold  ){
            cout << B.at(j) << endl; 
          }
          else{
            
              while( j - i >1){
        		     k = (j+i)/2;           
        	         if( counter( N, B.at(k), A)  <= threshold ){
           		       i= k ; 
        	         }
        	         else{
        	       	    j= k ;
       	             }
     	       }
            cout << B.at(i) << endl; 
//            cout << 50001 << endl; 
//            cout << i << j << endl; 
          }
          
     // for test
//     for(int i=0; i<101; i++ ){
//      cout << i << ":" << counter(N,i+1,A) - counter(N,i,A) <<endl;  
//     }
           
          // x is the candidate for the answer
    //	 cout <<  counter( N, 0, A)  << endl; 
        } 

Measured memory_bytes: 5776