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.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] a = new int[N];
        for (int i = 0; i < a.length; ++i) {
            a[i] = sc.nextInt();
        }

        System.out.println(solve(a));

        sc.close();
    }

    static int solve(int[] a) {
        long mLength = a.length * (a.length + 1L) / 2;

        int result = -1;
        int lower = Arrays.stream(a).min().getAsInt();
        int upper = Arrays.stream(a).max().getAsInt();
        while (lower <= upper) {
            int middle = (lower + upper) / 2;

            if (computeNonLessNum(a, middle) >= (mLength + 1) / 2) {
                result = middle;
                lower = middle + 1;
            } else {
                upper = middle - 1;
            }
        }

        return result;
    }

    static long computeNonLessNum(int[] a, int pivot) {
        int prefixSum = 0;
        int[] prefixSums = new int[a.length + 1];
        for (int i = 1; i < prefixSums.length; ++i) {
            prefixSum += (a[i - 1] >= pivot) ? 1 : -1;
            prefixSums[i] = prefixSum;
        }

        return computeNonInversionNum(prefixSums, 0, prefixSums.length - 1);
    }

    static long computeNonInversionNum(int[] values, int beginIndex, int endIndex) {
        if (beginIndex == endIndex) {
            return 0;
        }

        int middleIndex = (beginIndex + endIndex) / 2;
        long result = computeNonInversionNum(values, beginIndex, middleIndex)
                + computeNonInversionNum(values, middleIndex + 1, endIndex);
        List<Integer> sorted = new ArrayList<>();
        int leftIndex = beginIndex;
        int rightIndex = middleIndex + 1;
        while (leftIndex != middleIndex + 1 || rightIndex != endIndex + 1) {
            if (rightIndex == endIndex + 1
                    || (leftIndex != middleIndex + 1 && values[leftIndex] <= values[rightIndex])) {
                result += endIndex - rightIndex + 1;

                sorted.add(values[leftIndex]);
                ++leftIndex;
            } else {
                sorted.add(values[rightIndex]);
                ++rightIndex;
            }
        }

        for (int i = beginIndex; i <= endIndex; ++i) {
            values[i] = sorted.get(i - beginIndex);
        }

        return result;
    }
}