We will define the median of a sequence b of length M, as follows:

* Let b' be the sequence obtained by sorting b in non-decreasing order. Then, the value of the (M / 2 + 1)-th element of b' is the median of b. Here, / is integer division, rounding down.



For example, the median of (10, 30, 20) is 20; the median of (10, 30, 20, 40) is 30; the median of (10, 10, 10, 20, 30) is 10.

Snuke comes up with the following problem.

You are given a sequence a of length N. For each pair (l, r) (1 \leq l \leq r \leq N), let m_{l, r} be the median of the contiguous subsequence (a_l, a_{l + 1}, ..., a_r) of a. We will list m_{l, r} for all pairs (l, r) to create a new sequence m. Find the median of m.

Constraints

* 1 \leq N \leq 10^5
* a_i is an integer.
* 1 \leq a_i \leq 10^9

Input

Input is given from Standard Input in the following format:


N
a_1 a_2 ... a_N


Output

Print the median of m.

Examples

Input

3
10 30 20


Output

30


Input

1
10


Output

10


Input

10
5 9 5 9 8 9 3 5 4 3


Output

8
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Random;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author __shangu__
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        DMedianOfMedians solver = new DMedianOfMedians();
        solver.solve(1, in, out);
        out.close();
    }

    static class DMedianOfMedians {
        Random random = new Random(543534151132L + System.currentTimeMillis());
        private int[] ft;
        private int n;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            n = in.nextInt();
            int a[] = new int[n];
            for (int i = 0; i < n; ++i) a[i] = in.nextInt();
            int[] sorted = a.clone();
            mySort(sorted);

            int l = 0;
            int r = n;
            int cmp[] = new int[n];
            int presum[] = new int[n];
            ft = new int[n + 1];
            while (r - l > 1) {
                int mid = (l + r) / 2, cur = sorted[mid];
                for (int i = 0; i < n; ++i) {
                    if (a[i] >= cur) cmp[i] = 1;
                    else cmp[i] = -1;
                }
                presum[0] = cmp[0];
                int offset = cmp[0];
                for (int i = 1; i < n; ++i) {
                    presum[i] = presum[i - 1] + cmp[i];
                    offset = Math.min(offset, presum[i]);
                }
                offset = 1 - offset;

                for (int i = 0; i <= n; ++i) ft[i] = 0;
                long cnt = 0;
                for (int i = 0; i < n; ++i) {
                    cur = presum[i] + offset;
                    cnt += sum(cur);
                    if (presum[i] >= 0) ++cnt;
                    update(cur, 1);
                }

                if (cnt >= ((long) (1 + n) * n / 2 + 1) / 2) l = mid;
                else r = mid;
            }
            out.println(sorted[l]);
        }

        private int lowbit(int x) {
            return x & (-x);
        }

        private long sum(int x) {
            long ans = 0;
            while (x > 0) {
                ans += ft[x];
                x -= lowbit(x);
            }
            return ans;
        }

        private void update(int x, int d) {
            while (x <= n) {
                ft[x] += d;
                x += lowbit(x);
            }
        }

        private void mySort(int[] s) {
            for (int i = 0; i < s.length; ++i) {
                int j = random.nextInt(i + 1);
                int t = s[i];
                s[i] = s[j];
                s[j] = t;
            }
            Arrays.sort(s);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

