#PY0026. 中位数的中位数

中位数的中位数

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.