该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给你一个序列。对于每个区间[l,r]都会有一个中位数，为x[len/2+1]。

所以共有(1+n)*n/2个中位数，这些中位数再取中位数。问你这个中位数是多少。

Format

Input

一行给出数字N. 接下来一行N个数字Xi，代表这个数列

1≤N≤100000

1≤Xi≤10^9

Output

如题

Samples

3
10 30 20

30

Hint

数列 (10) 的中位数 10.

数列 (30) 的中位数 30.

数列 (20) 的中位数 20.

数列 (10,30) 的中位数 30.

数列 (30,20) 的中位数 30.

数列 (10,30,20) 的中位数 20.

于是对于数列(10,30,20,30,30,20) 其中位数为 30.