Background

Special for beginners, ^_^

Description

定义中位数为升序排序后中间的那个数，如果有偶数个数，则为较大的那个中间数。

给出一个不超过 $10^6$ 个数的数组，求所有子段的中位数的中位数。

Format

Input

第一行一个正整数 $N（\le10^6）$。

第二行 $N$ 个不超过 $10^9$ 的正整数。

Output

所有子段的中位数的中位数。

Samples

3
1 3 2

3

Limitation

1s, 1024KiB for each test case.