众所周知我们可爱的智慧之神纳西妲在约 $500$ 年前就成为了草神并入坑 OI。由于其具有极高的智慧，即使公务繁忙，她也能抽出时间来学 OI，因此她进度非常的快。

结果是，另一个二次元老哥——洛天依也染上了 OI 并无法自拔，于是来到提瓦特旅游时慕名拜访了纳西妲，并问了一道她不会的题。

题目描述

洛天依有一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$。她可以进行以下操作任意多次（可能为 $0$）：

• 选择一段子区间 $[l,r](1 \le l \le r \le n)$，将 $a_l,a_{l+1},\dots,a_r$ 全部改成这些数的中位数。

这里，一个子区间 $[l,r]$ 的中位数的定义为该区间内的数降序排序后的第 $\lceil\frac{r-l+1}{2}\rceil$ 项。

现在洛天依想问，操作之后序列的最小值最大可以是多少。纳西妲作为学了近 $500$ 年 OI 的智慧之神，当然把这题秒了。但是数据范围有点大，用神之心跑不动，须弥又没有键盘，所以她只好请你帮忙把程序输到洛天依的脑子里。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数，表示 $a_1,a_2,\dots,a_n$。

输出格式

一行一个整数表示答案。

输入输出样例 #1

输入 #1

7
1 9 1 9 8 1 0

输出 #1

9

输入输出样例 #2

说明/提示

显然我们依次进行如下操作：

数据规模与约定

对于 $100\%$ 的数据，$n \le 2\times10^6,0 \le a_i \le 10^{18}$。