P11761 [IAMOI R1] 明码标价

小 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

无

无

### 样例解释 共有 $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$ | $40$ | 无 | $20$ | | $4$ | $100$ | A | $23$ | | $5$ | $100$ | 无 | $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$ 的整数。