#P16923. [Ontak2026maly]金字塔

[Ontak2026maly]金字塔

题目描述

Byteotia 的社会结构可以看作一座共有 nn 层的金字塔。各层自上而下编号为 1,2,…,n1,2,\ldots,n。

第 kk 层共有 2k−12k-1 个位置。

最底层,也就是第 nn 层的每个位置已经给定一个整数值。上面的每一层都由其下一层构造得到。

具体来说,假设某一层当前从左到右的数为

a1,a2,…,a2d+1a_1,a_2,\ldots,a_{2d+1},

那么它正上方一层的 2d−12d-1 个数依次为

$\operatorname{med}(a_1,a_2,a_3),\operatorname{med}(a_2,a_3,a_4),\ldots,\operatorname{med}(a_{2d-1},a_{2d},a_{2d+1})$,

其中 med⁡(x,y,z)\operatorname{med}(x,y,z) 表示三个数的中位数。

不断执行这一过程,最终第 11 层只剩下一个数。

你的任务是求出金字塔顶端这个数的值。

输入格式

第一行包含一个整数 nn,表示金字塔的层数:

2≤n≤1000002\le n\le100000。

第二行包含 2n−12n-1 个整数 aia_i,表示最底层从左到右的初始数值:

−109≤ai≤109-10^9\le a_i\le10^9。

输出格式

输出一个整数,表示最终位于金字塔顶端的数值。

子任务

附加限制 分值
输入的数已经排好序 7
n≤1000n\le1000 16
ai∈{0,1}a_i\in\{0,1\} 21
对所有 ii 均有 ai>0a_i>0 35
无附加限制 21

样例

5
5 3 6 1 2 9 7 8 4
2

说明

对于样例,最底层为:

5 3 6 1 2 9 7 8 4

第一轮取连续三个数的中位数后得到:

5 3 2 2 7 8 7

继续按照同样的规则逐层缩短,最终顶端的值为 22。