Алиса и Боб придумали довольно странную игру. У них есть массив целых чисел \(a_1, a_2,\ldots, a_n\). Алиса выбирает некоторое целое число \(k\) и сообщает его Бобу, после чего происходит следующее:
- Боб выбирает два целых числа \(i\) и \(j\) (\(1 \le i < j \le n\)), а затем ищет максимум среди чисел \(a_i, a_{i + 1},\ldots, a_j\);
- Если полученный максимум строго больше \(k\), то побеждает Алиса, иначе Боб.
Помогите Алисе узнать максимальное \(k\), при котором она гарантированно побеждает.
Примечание
В первом наборе входных данных всевозможные подотрезки, которые может выбрать Боб, выглядят следующим образом: \([2, 4], [2, 4, 1], [2, 4, 1, 7], [4, 1], [4, 1, 7], [1, 7]\). Максимумы на подотрезках соответственно равны \(4, 4, 7, 4, 7, 7\). Можно показать, что \(3\) является наибольшим целым числом, таким что любой из максимумов будет строго больше него.
В третьем наборе входных данных единственным отрезком, который может выбрать Боб, является \([1, 1]\). Поэтому ответ равен \(0\).