Description

There are $n$ items in the mall, where the $i$-th item has price $a_i$. Since Xiao C has decision fatigue, Xiao L wants to select an item through the following method:

Xiao L neither wants the cheapest item (poor quality) nor the most expensive one (low cost-effectiveness). Therefore, he defines the median of $m$ item prices as the price of the middle item after sorting prices in ascending order. Specifically, the median is the price of the $\lfloor\frac{m+1}{2}\rfloor$-th item after sorting.

Xiao L plans to divide these $n$ items into continuous $k$ segments based on their utility, then take the median-priced item from each segment. Next, he will take the median of these selected items as the final purchase choice.

However, Xiao C disagrees with this plan because her partitioning differs from Xiao L's. They compromise by adopting the fairest approach: considering all possible partitioning schemes, collect all possible median prices (including duplicates from multiple schemes), then take the median of this collection as the final price.

Given the complexity of possible partitions, they need your help to determine the final selected price.

Formal Problem Statement

Define $\operatorname{mid}(\{a_1,a_2,\cdots,a_n\})$ as the median of multiset $\{a_1,\cdots,a_n\}$, which equals the $\lfloor\frac{n+1}{2}\rfloor$-th element after sorting in ascending order.

Given a sequence $a_1\sim a_n$ of length $n$, define $f(l,r)=\operatorname{mid}(\{a_l,a_{l+1},\cdots,a_r\})$.

A partition is defined as:

• A sequence $l$ of length $k$ (where $0 \le k \le n$) satisfying $1 \le l_1 < l_2 < \cdots < l_k < n$ when $k \neq 0$.
• Two partitions are different if their $k$ values differ or any position in $l$ differs.

The weight of a partition is:

• When $k \neq 0$: $\operatorname{mid}(\{f(1,l_1), f(l_1+1,l_2), \cdots, f(l_k+1,n)\})$
• When $k = 0$: $\operatorname{mid}(\{f(1,n)\})$

Find the median of the multiset containing weights of all distinct partitions.

Input Format

• The first line contains a single integer $n$.
• The second line contains $n$ integers $a_1\sim a_n$.

Output Format

Output a single integer representing the final selected price.

3
1 2 3

1

Hint

Sample Explanation

For $n=3$, there are 4 partition schemes:

1. $\{\{1\},\{2\},\{3\}\}$ → weight $\operatorname{mid}(1,2,3)=2$
2. $\{\{1,2\},\{3\}\}$ → weight $\operatorname{mid}(1,3)=1$
3. $\{\{1\},\{2,3\}\}$ → weight $\operatorname{mid}(1,2)=1$
4. $\{\{1,2,3\}\}$ → weight $\operatorname{mid}(2)=2$

The final multiset is $\{1,1,2,2\}$ with median $1$.

Constraints

Subtask scoring is used.

Special Property A: $a$ is a permutation of $1\sim n$.

For all data: $2 \le n \le 100$, $1 \le a_i \le 10^9$.

Note: In C++, you may use __int128 to store integers in $[-2^{128}, 2^{128}-1]$.

Translation by DeepSeek R1