题目背景

小 C 拉小 L 去买东西。

题目描述

商场里有 $n$ 个商品，第 $i$ 个商品的价格为 $a_i$。由于小 C 具有选择困难症，所以小 L 想通过以下方式挑选购买一个商品：

小 L 既不想要选择最便宜的商品（质量差），也不想要选择最贵的商品（性价比低），于是，他定义 $m$ 个商品价格的中位数为按照价格从小排序后最中间的商品价格。具体的说，排序后第 $\lfloor\frac{m+1}{2}\rfloor$ 个商品的价格就是这 $m$ 个商品价格的中位数。

同时，小 L 准备把这 $n$ 个商品按照用处分为连续的 $k$ 段，并在每段中取出价格为中位数的商品。接下来，他再次取出这些商品之中价格为中位数的商品，选出这个唯一的商品购买。

然而小 C 似乎并不同意这个方案，原因是小 C 的划分与小 L 的划分并不相同。于是，他们决定各退一步，采取最公平的方式选择商品。具体的，他们找出按照任意划分方案而得出的商品价格（可能存在一个商品被找出多次，也要计算多次），再次取出价格为中位数的商品，选出这个唯一的商品购买。

然而划分的方案可能有很多种，小 L 和小 C 被绕晕了。所以，他们想请你帮忙，他们最后选出的商品价格是多少？

形式化题意

定义 $\operatorname{mid}(\{a_1,a_2,\cdots,a_n\})$ 表示在可重集合中 $a_1\sim a_n$ 的中位数。形式化地来说，$a_1\sim a_n$ 的中位数为将 $a_1$ 到 $a_n$ 从小到大排序后， $a_{\lfloor\frac{n+1}{2}\rfloor}$ 的值。

现有一个长度为 $n$ 的数列 $a_1\sim a_n$。定义了 $f(l,r)=\operatorname{mid}(\{a_l,a_{l+1},\cdots,a_r\})$。

定义划分和划分的权值：

• 一个划分被定义为一个长度为任意一个在 $[0,n]$ 的整数 $k$ 的序列 $l$，满足 $1\ {\color{red}{\le}}\ l_1<l_2<\cdots<l_k<n$。

• 两个划分不同当且仅当两个划分的 $k$ 不相同或者存在一个位置使得两个划分的 $l$ 不相同。

• 当 $k\not=0$ 时，划分的权值是 $\operatorname{mid}(\{f(1,l_1),f(l_1+1,l_2),\cdots,f(l_k+1,n)\})$。

• 否则，划分的权值是 $\operatorname{mid}(\{f(1,n)\})$。

求所有互不相同的划分权值的可重集合的 $\operatorname{mid}$。

输入格式

第一行，共一个整数 $n$。

第二行，共 $n$ 个整数，表示 $a_1\sim a_n$。

输出格式

共一个整数，表示最后选出的商品价格。

3
1 2 3

1

提示

样例解释

共有 $4$ 种划分方案，分别为 $\{\{1\},\{2\},\{3\}\},\{\{1,2\},\{3\}\},\{\{1\},\{2,3\}\},\{\{1,2,3\}\}$，其中：

$\operatorname{mid}(\{1\})=1,\operatorname{mid}(\{2\})=2,\operatorname{mid}(\{3\})=3,\operatorname{mid}(\{1,2\})=1,\operatorname{mid}(\{2,3\})=2,\operatorname{mid}(\{1,2,3\})=2$；

这 $4$ 种划分的权值分别为 $\operatorname{mid}(\{1,2,3\})=2,\operatorname{mid}(\{1,3\})=1,\operatorname{mid}(\{1,2\})=1,\operatorname{mid}(\{2\})=2$；

最终答案即为 $\operatorname{mid}(\{1,1,2,2\})=1$。

数据范围

本题采用捆绑测试。

Subtask	$n\le$	特殊性质	分值
$1$	$15$	无	$13$
$2$	$40$	A	$17$
$3$		无	$20$
$4$	$100$	A	$23$
$5$		无	$27$

特殊性质 A：保证 $a$ 为一个 $1\sim n$ 的排列。

对于所有数据，保证 $2\le n\le 100$，$1\le a_i\le 10^9$。

注：在 C++ 语言中，你可以使用类型 __int128 来存储范围在 $-2^{128}\sim 2^{128}-1$ 的整数。