#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>

using namespace std;

template <class T>
class memory_pool {
    public:
    memory_pool(int num) : index_size(0), pool(NULL) {
        add_pool(num, num);
    }
    
    ~memory_pool() {
        for (int i = 0; i < index_size; i++) delete[] index[i];
        free(pool);
    }
    
    T *allocate() {
        if (pool_size == 0) add_pool(max_size, max_size * 2);
        return pool[--pool_size];
    }
    
    void deallocate(T* element) {
        pool[pool_size++] = element;
    }
    
    void swap(memory_pool& other) {
        std::swap(pool_size, other.pool_size);
        std::swap(max_size, other.max_size);
        std::swap(index_size, other.index_size);
        std::swap(pool, other.pool);
        std::swap(index, other.index);
    }
    
    private:
    int pool_size;
    int max_size;
    int index_size;
    T** pool;
    T* index[30];
    
    void add_pool(int new_pool_size, int new_max_size) {
        pool_size = new_pool_size;
        max_size = new_max_size;
        T* tmp = new T[pool_size];
        free(pool);
        pool = (T**)malloc(sizeof(T*) * max_size);
        for (int i = 0; i < pool_size; i++) pool[i] = &tmp[i];
        index[index_size++] = tmp;
    }
};

template <class Key>
class mymultiset {
    public:    
    mymultiset(int num = 1) : top(NULL), pool(num) {}
    mymultiset(const initializer_list<Key>& list);
    bool empty() const;
    int size() const;
    void clear();
    void insert(const Key& key);
    void erase(const Key& key);
    void swap(mymultiset& other);
    int count(const Key& key) const;
    int find(const Key& key) const;
    Key rank(int n) const;
    int lower_bound(const Key& key) const;
    int upper_bound(const Key& key) const;
    int rlower_bound(const Key& key) const;
    int rupper_bound(const Key& key) const;
    
    private:
    struct entry {
        Key key;
        int size;
        int height;
        struct entry* child[2];
    };
    memory_pool <entry> pool;
    entry* top;
    int change;
    int size(const entry* now) const;
    int height(const entry* now) const;
    void adjust(entry* now);
    entry* rotate(entry* now, int direction);
    entry* rotate_double(entry* now, int direction);
    entry* balance(entry* now, int direction, bool add);
    entry* insert(entry* now, const Key& key);
    entry* erase(entry* now, const Key& key);
    entry* erase_max(entry* now, entry** up);
};

template <class Key> mymultiset<Key>::mymultiset(const initializer_list<Key>& list) : top(NULL), pool(list.size()) {
    for (typename initializer_list<Key>::iterator it = list.begin(); it != list.end(); it++) insert(*it);
}

template <class Key> bool mymultiset<Key>::empty() const {
    return top == NULL;
}

template <class Key> int mymultiset<Key>::size() const {
    return size(top);
}

template <class Key> void mymultiset<Key>::clear() {
    int num = size(top);
    if (num == 0) return;
    vector <entry*> elements;
    elements.reserve(num);
    elements.push_back(top);
    for (int i = 0; i < num; i++) {
        pool.deallocate(elements[i]);
        if (elements[i]->child[0] != NULL) elements.push_back(elements[i]->child[0]);
        if (elements[i]->child[1] != NULL) elements.push_back(elements[i]->child[1]);
    }
    top = NULL;
}

template <class Key> void mymultiset<Key>::insert(const Key& key) {
    top = insert(top, key);
}

template <class Key> void mymultiset<Key>::erase(const Key& key) {
    top = erase(top, key);
}

template <class Key> void mymultiset<Key>::swap(mymultiset& other) {
    std::swap(top, other.top);
    pool.swap(other.pool);
}

template <class Key> int mymultiset<Key>::count(const Key& key) const {
    return upper_bound(key) - lower_bound(key);
}

template <class Key> int mymultiset<Key>::find(const Key& key) const {
    int count = 0;
    int first = size(top);
    entry* now = top;
    while (true) {
        if (now == NULL) {
            return first;
        } else if (key < now->key) {
            now = now->child[0];
        } else if (key == now->key) {
            first = size(now->child[0]) + count;
            now = now->child[0];
        } else {
            count += size(now->child[0]) + 1;
            now = now->child[1];
        }
    }
}

template <class Key> Key mymultiset<Key>::rank(int n) const {
    entry* now = top;
    while (true) {
        int num = size(now->child[0]);
        if (n < num) {
            now = now->child[0];
        } else if (n == num) {
            return now->key;
        } else {
            n -= num + 1;
            now = now->child[1];
        }
    }
}

template <class Key> int mymultiset<Key>::lower_bound(const Key& key) const {
    int count = 0;
    entry* now = top;
    while (true) {
        if (now == NULL) {
            return count;
        } else if (key <= now->key) {
            now = now->child[0];
        } else {
            count += size(now->child[0]) + 1;
            now = now->child[1];
        }
    }
}

template <class Key> int mymultiset<Key>::upper_bound(const Key& key) const {
    int count = 0;
    entry* now = top;
    while (true) {
        if (now == NULL) {
            return count;
        } else if (key < now->key) {
            now = now->child[0];
        } else {
            count += size(now->child[0]) + 1;
            now = now->child[1];
        }
    }
}

template <class Key> int mymultiset<Key>::rlower_bound(const Key& key) const {
    int count = size(top) - 1;
    entry* now = top;
    while (true) {
        if (now == NULL) {
            return count;
        } else if (key < now->key) {
            count -= size(now->child[1]) + 1;
            now = now->child[0];
        } else {
            now = now->child[1];
        }
    }
}

template <class Key> int mymultiset<Key>::rupper_bound(const Key& key) const {
    int count = size(top) - 1;
    entry* now = top;
    while (true) {
        if (now == NULL) {
            return count;
        } else if (key <= now->key) {
            count -= size(now->child[1]) + 1;
            now = now->child[0];
        } else {
            now = now->child[1];
        }
    }
}

template <class Key> inline int mymultiset<Key>::size(const entry* now) const {
    return now == NULL ? 0 : now->size;
}

template <class Key> inline int mymultiset<Key>::height(const entry* now) const {
    return now == NULL ? 0 : now->height;
}

template <class Key> inline void mymultiset<Key>::adjust(entry* now) {
    now->size = size(now->child[0]) + size(now->child[1]) + 1;
    now->height = max(height(now->child[0]), height(now->child[1])) + 1;
}

template <class Key> inline typename mymultiset<Key>::entry* mymultiset<Key>::rotate(entry* now, int direction) {
    entry* tmp = now->child[1 - direction];
    now->child[1 - direction] = tmp->child[direction];
    tmp->child[direction] = now;
    adjust(now);
    adjust(tmp);
    return tmp;
}

template <class Key> inline typename mymultiset<Key>::entry* mymultiset<Key>::rotate_double(entry* now, int direction) {
    entry* tmp = now->child[direction];
    entry* tmp2 = tmp->child[1 - direction];
    tmp->child[1 - direction] = tmp2->child[direction];
    now->child[direction] = tmp2->child[1 - direction];
    tmp2->child[direction] = tmp;
    tmp2->child[1 - direction] = now;
    adjust(tmp);
    adjust(now);
    adjust(tmp2);
    return tmp2;
}

template <class Key> inline typename mymultiset<Key>::entry* mymultiset<Key>::balance(entry* now, int direction, bool add) {
    if (change < 2) {
        now->size += change;
    } else {
        int origin = now->height;
        if (height(now->child[direction]) - height(now->child[1 - direction]) == 2) {
            if (height(now->child[direction]->child[1 - direction]) > height(now->child[direction]->child[direction])) {
                now = rotate_double(now, direction);
            } else {
                now = rotate(now, 1 - direction);
            }
        } else {
            adjust(now);
        }
        if (origin == now->height) change = add ? 1 : -1;
    }
    return now;
}

template <class Key> inline typename mymultiset<Key>::entry* mymultiset<Key>::insert(entry* now, const Key& key) {
    if (now == NULL) {
        change = 2;
        entry* tmp = pool.allocate();
        tmp->key = key;
        tmp->size = tmp->height = 1;
        tmp->child[0] = tmp->child[1] = NULL;
        return tmp;
    } else if (key <= now->key) {
        now->child[0] = insert(now->child[0], key);
        return balance(now, 0, true);
    } else {
        now->child[1] = insert(now->child[1], key);
        return balance(now, 1, true);
    }
}

template <class Key> inline typename mymultiset<Key>::entry* mymultiset<Key>::erase(entry* now, const Key& key) {
    if (now == NULL) {
        change = 0;
        return now;
    } else if (key < now->key) {
        now->child[0] = erase(now->child[0], key);
        return balance(now, 1, false);
    } else if (key == now->key) {
        entry* up;
        if (now->child[0] == NULL || now->child[1] == NULL) {
            change = 2;
            up = (now->child[0] == NULL) ? now->child[1] : now->child[0];
        } else {
            entry* tmp = erase_max(now->child[0], &up);
            up->size = now->size;
            up->height = now->height;
            up->child[0] = tmp;
            up->child[1] = now->child[1];
            up = balance(up, 1, false);
        }
        pool.deallocate(now);
        return up;
    } else {
        now->child[1] = erase(now->child[1], key);
        return balance(now, 0, false);
    }
}

template <class Key> inline typename mymultiset<Key>::entry* mymultiset<Key>::erase_max(entry* now, entry** up) {
    if (now->child[1] == NULL) {
        change = 2;
        *up = now;
        return now->child[0];
    } else {
        now->child[1] = erase_max(now->child[1], up);
        return balance(now, 0, false);
    }
}


int a[100000];
int b[100000];

int main() {
    int n, l, r, m, i;
    vector <pair<int, int>> v;
    
    scanf("%d", &n);
    
    for (i = 0; i < n; i++) scanf("%d", &a[i]);
    
    for (i = 0; i < n; i++) v.push_back(make_pair(a[i], i));
    
    sort(v.begin(), v.end());
    
    l = 0, r = n, m = (l + r) / 2;
    
    while (r - l > 1) {
        int x = v[m].second, sum = 0;
        long long c1 = 0, c2 = 0;
        mymultiset <int> s;
        
        for (i = 0; i < n; i++) {
            if (a[i] < a[x] || (a[i] == a[x] && i < x)) {
                b[i] = -1;
            } else {
                b[i] = 1;
            }
        }
        
        for (i = 0; i < n; i++) {
            int p;
            
            sum += b[i];
            s.insert(b[i] - sum);
            
            p = s.lower_bound(-sum);
            
            c1 += p;
            c2 += (i + 1) - p;
        }
        
        if (c1 <= c2) {
            l = m;
            m = (l + r) / 2;
        } else {
            r = m;
            m = (l + r) / 2;
        }
    }
    
    printf("%d\n", v[l].first);
    
    return 0;
}


Measured memory_bytes: 7820