#include <bits/stdc++.h>

namespace stdv = std::views;
namespace stdr = std::ranges;

using i64 = long long;

template<typename A, typename B>
constexpr bool chmax(A& a, const B& b) {
    a = (a > b) ? a : b;
    return a == b;
}
template<typename A, typename B>
constexpr bool chmin(A& a, const B& b) {
    a = (a < b) ? a : b;
    return a == b;
}
int lg(unsigned int x) {
    return std::bit_width(x) - 1;
}

template<typename T = int>
class Fenwick {
private:
    int n;
    std::vector<T> tr;
    struct Proxy {
        Fenwick<T>& fen{};
        int idx{};
        constexpr Proxy& operator+=(const T& v) {
            fen.add(idx, v);
            return *this;
        }
        constexpr Proxy& operator-=(const T& v) {
            fen.add(idx, -v);
            return *this;
        }
        constexpr Proxy& operator++() {
            fen.add(idx, 1);
            return *this;
        }
        constexpr Proxy& operator++(int) {
            fen.add(idx, 1);
            return *this;
        }
        constexpr Proxy& operator--() {
            fen.add(idx, -1);
            return *this;
        }
        constexpr Proxy& operator--(int) {
            fen.add(idx, -1);
            return *this;
        }
    };
public:
    explicit Fenwick(int n = 0, const T& init_ = T()) {
        init(n);
        for (int i = 0; i < n; i++) {
            add(i, init_);
        }
    }
    explicit Fenwick(const std::vector<T>& init_) {
        init(init_);
    }
    void init(int n_) {
        n = n_;
        tr.assign(n, {});
    }
    void init(const std::vector<T>& init_) {
        init(init_.size());
        for (int i = 0; i < n; i++) {
            add(i, init_[i]);
        }
    }
    void add(int x, const T& v) {
        for (++x; x <= n; x += x & -x) {
            tr[x - 1] += v;
        }
    }
    T sum(int x) {
        T ans = T();
        for (; x; x -= x & -x) {
            ans += tr[x - 1];
        }
        return ans;
    }
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
    int find(const T& k) {
        int x = 0;
        T cur{};
        for (int i = 1 << lg(n); i; i /= 2) {
            if (x + i <= n && cur + tr[x + i - 1] <= k) {
                x += i;
                cur = cur + tr[x - 1];
            }
        }
        return x;
    }
    constexpr Proxy operator[](int i) {
        return Proxy{ *this, i };
    }
    constexpr T operator() (int r) {
        return sum(r);
    }
    constexpr T operator() (int l, int r) {
        return rangeSum(l, r);
    }
};

int main(int argc, const char* argv[]) {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    auto V = a;
    std::sort(V.begin(), V.end());
    V.erase(std::unique(V.begin(), V.end()), V.end());
    const int m = V.size();

    for (int i = 0; i < n; i++) {
        a[i] = std::lower_bound(V.begin(), V.end(), a[i]) - V.begin();
    }

    std::vector b(n, std::vector<int>(n));
    for (int i = 0; i < n; i++) {
        Fenwick fen(m);
        for (int j = i; j < n; j++) {
            fen[a[j]]++;
            int len = j - i + 1;
            int k = (len + 1) / 2 - 1;
            b[i][j] = fen.find(k);
        }
    }

    auto check = [&](int v) {
        std::vector s(n + 1, std::vector<int>(n + 1));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int w = (b[i][j] <= v ? 1 : -1);
                if (j < i) {
                    w = 0;
                }
                s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + w;
            }
        }

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int w = s[j + 1][j + 1] - s[i][j + 1] - s[j + 1][i] + s[i][i];
                if (w >= 0) {
                    cnt++;
                } else {
                    cnt--;
                }
            }
        }
        return cnt < 0;
    };

    int l = -1, r = m - 1;
    while (l < r) {
        int mid = (l + r + 1) / 2;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }

    std::cout << V[l + 1] << "\n";

    return 0;
}