U227882 [sxyz NOIP 模拟赛]2 中位数（medium）

[sxyz NOIP 模拟赛]2 中位数（medium）T2 ------------ 1s 512MB

这是一道简单的中位数问题。 给定 n 个整数，其中第 i 个整数是 ai。你需要从中选出若干个整数，使得所有相邻的两个整数至少被选择了一个。 你需要最大化你选择的卡片的中位数，并输出这个最大值。在本题中， n 个数的中位数是这 n 个数中从小到大第 $\dfrac{n}{2}$ 上取整个元素。

第一行一个整数 n 第二行 n 个整数 ai

一行一个整数，表示中位数的最大值。

2.4 数据范围与提示 对于 30% 的数据， n ≤ 20 另有 20% 的数据， ai ≤ 1 对于所有数据， 1 ≤ n ≤ 2 ∗ 10$^5$, 0 ≤ ai ≤ 10$^9$