Визначимо медіану деякої послідовності цілих чисел \(b\) довжиною \(M\) таким чином:

• Нехай \(b`\) - відсортована у порядку спадання послідовність \(b\). Тоді на \((M / 2 + 1)\) місці послідовності \(b`\) знаходиться медіана послідовності \(b\). Тут ділення ціле і округлюється число донизу.

Наприклад, медіана (10, 30, 20) - 20; медіана (10, 30, 20, 40) дорівнює 30; медіана (10, 10, 10, 20, 30) дорівнює 10.

Задається послідовність \(a\), яка містить \(N\) цілих чисел. Для кожної пари (\(l, r\)) (\(1 \le l \le r \le N\)) нехай \(m_{l, r}\) - медіана підпослідовності (\(a_l, a_{l + 1}, ..., a_r\)) чисел з \(a\).

Утворимо послідовність \(m\), яка містить медіани \(m_{l, r}\) для всіх пар (\(l, r\)). Знайдіть медіану послідовності \(m\)

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число \(N\) (\(1 \le N \le 10^5\)).

Наступний рядок містить цілі числа \(a_i\) (\(1 \le a_i \le 10^9\)), які розділяються пропуском.

Формат вихідних даних

Вивести медіану описаної послідовності \(m\)

Приклад вхідних даних

3
10 30 20

Приклад вихідних даних

30

Пояснення

Медіани кожної підпослідовності \(a\) такі:

Медіана (10) дорівнює 10.

Медіана (30) - 30.

Медіана (20) - 20.

Медіана (10, 30) дорівнює 30.

Медіана (30, 20) дорівнює 30.

Медіана (10, 30, 20) дорівнює 20.

Таким чином, \(m\) = (10, 30, 20, 30, 30, 20), а медіана \(m\) буде 30.