Мокка любит массивы, поэтому перед отъездом Чамо подарил ей массив \(a\), состоящий из \(n\) целых положительных чисел.
Мокка не любит массивы, содержащие разные числа, поэтому Мокка решила использовать магию, чтобы изменить массив. Мокка может выполнить следующую трехэтапную операцию несколько (возможно, ноль) раз:
- Выбрать индексы \(l\) и \(r\) (\(1 \leq l < r \leq n\))
- Пусть \(x\) — медиана\(^\dagger\) подмассива \([a_l, a_{l+1},\ldots, a_r]\)
- Сделать все значения \(a_l, a_{l+1},\ldots, a_r\) равными \(x\)
Предположим, что изначально \(a=[1,2,3,4,5]\):
- Если Мокка на первой операции выберет \((l,r)=(3,4)\), то \(x=3\), массив изменится на \(a=[1,2,3,3,5]\).
- Если Мокка на первой операции выберет \((l,r)=(1,3)\), то \(x=2\), массив изменится на \(a=[2,2,2,4,5]\).
Мокка будет выполнять операции до тех пор, пока все элементы массива не станут равными одному числу. Мокка хочет узнать, чему равняется максимально возможное значение этого числа.
\(^\dagger\) Медиана в массиве \(b\) длины \(m\) — это элемент, занимающий позицию номер \(\lfloor \frac{m+1}{2} \rfloor\) после сортировки элементов в неубывающем порядке. Например, медиана \([3,1,4,1,5]\) равна \(3\), а медиана \([5,25,20,24]\) равна \(20\).
Примечание
В первом наборе входных данных \(a=[1,2]\). Мокка может выбрать только интервал \((l,r)=(1,2)\). Массив будет изменен на \(a=[1,1]\). Поэтому ответом будет \(1\).
Со вторым набором входных данных Мокка может выполнить следующие операции:
- Выбрать интервал \((l,r)=(4,5)\), тогда \(a=[1,2,3,4,4]\).
- Выбрать интервал \((l,r)=(3,5)\), тогда \(a=[1,2,4,4,4]\).
- Выбрать интервал \((l,r)=(1,5)\), тогда \(a=[4,4,4,4,4]\).
Все элементы массива равны \(4\). Можно доказать, что максимальное значение конечного числа не может быть больше \(4\).