Однажды Робин Гуд нашёл массив из $$$n$$$ целых чисел. Он непременно решил уравнять этот массив, то есть сделать все элементы равными. Для этого он может выполнить над массивом несколько (возможно ноль) операций.

За одну операцию Робин Гуд может выбрать три подряд идущих элемента массива и заменить их на медиану этих трёх элементов.

Медианой набора чисел $$$a_1, a_2, \ldots, a_{2m-1}$$$ называется число $$$c_m$$$, где $$$c_1, c_2, \ldots, c_{2m-1}$$$ — набор чисел $$$a_1, a_2, \ldots, a_{2m-1}$$$, отсортированный по неубыванию. Например, медиана набора чисел $$$5, 2, 3$$$ равна $$$3$$$, а медиана набора чисел $$$4, 8, 4$$$ равна $$$4$$$.

Можно показать, что такими операциями всегда можно уравнять массив длины хотя бы $$$3$$$. Например, массив $$$[2, 4, 5, 5, 9]$$$ можно уравнять так: $$$[2, 4, 5, 5, 9] \to [2, 5, 5, 5, 9] \to [5, 5, 5, 5, 9] \to [5, 5, 5, 5, 5]$$$.

Робин Гуд хочет узнать максимальное число, к которому можно приравнять все элементы массива с помощью нескольких применений вышеописанной операции.