Fair Product Selection

You are given an array of n products with prices a₁,a₂,…,a_n. For any contiguous subarray a_l,a_l+1,…,a_r we define a function

[ f(l, r)=\operatorname{mid}({a_l,a_{l+1},\cdots,a_r}) ]

where the median of a multiset of m numbers is defined as follows. Sort the numbers in non‐decreasing order and choose the element at position

[ \left\lfloor \frac{m+1}{2} \right\rfloor ]

(for example, the median of two numbers is the smaller one).

A partition of the array is defined by choosing an integer k (with 0 ≤ k < n) and then selecting a sequence of indices

[ 1 \le l_1 < l_2 < \cdots < l_k < n ]

which splits the array into k+1 contiguous segments:

• Segment 1: indices 1 to l₁
• Segment 2: indices l₁+1 to l₂
• \(\vdots\)
• Segment k+1: indices l_k+1 to n

For a partition with k ≥ 1, its weight is defined as the median of the list of values

[ {f(1,l_1),; f(l_1+1,l_2),; \cdots,; f(l_k+1,n)} ]

and for the case k=0 (i.e. no partition), the weight is defined to be f(1,n).

Let \(S\) be the multiset of the weights of all possible partitions (note that if a weight appears from different partitions it is counted with multiplicity). Your task is to compute the median of \(S\), i.e. if \(S\) has \(M\) elements (where \(M=2^{n-1}\)), then after sorting \(S\) in non-decreasing order, you should output the element at position

[ \left\lfloor \frac{M+1}{2} \right\rfloor\text{.} ]

Hint: It turns out that the final answer can be determined solely from the sorted order of the array. In particular, if we let

[ b_1 \le b_2 \le \cdots \le b_n ]

be the sorted prices, then the answer is b_{\lceil\frac{n+1}{4}\rceil} (using 1-indexing). For example, if n = 4 and the prices are [4,1,3,2] (so that (b=[1,2,3,4])), then the answer is b₂ = 2.

Input Constraints:

• 1 ≤ n ≤ 10⁵
• 1 ≤ a_i ≤ 10⁹

Output: Output the final chosen product price.

inputFormat

The first line contains a single integer n, the number of products. The second line contains n space-separated integers a₁,a₂,…,aₙ representing the price of each product.

outputFormat

Output a single integer — the price of the product selected by the fair scheme.

sample

1
5

5