Задача B. Удачный выбор

Задачу добавил: alef

Успешно сдано решений: 212

Ограничения: время на тест - 2с, память - 256 Мб

Очень Мудрый Руководитель решил посетить магазин компьютерной техники. Он шел вдоль длинной витрины с трансформерпадами новой линейки "ЯСам" (ISome) и, хотя он внешне выглядел спокойным, менеджеры чувствовали, что он чем-то недоволен.
- А почему трансформерпады выставлены именно в таком порядке? - поинтересовался Очень Мудрый Руководитель.
- А мы меняем порядок. Часто. По расцветке корпуса группируем, по набору интерфейсов...
- И как это отражается на продажах?
- Почти никак. Покупатели все равно проходят вдоль всей витрины, чтобы увидеть все модели, а потом обращаются к консультанту.
- Это неправильно, - заметил Очень Мудрый Руководитель. - Ведь мы задумывали ЯСам как очень простое устройство, с которым легко может работать даже маленький ребенок. Когда человек выбирает устройство с помощью консультанта, он не будет считать его простым. Нужно, чтобы он выбрал его сам. И был доволен своим выбором.
И тут Очень Мудрый Руководитель дал очень мудрый совет распорядителю торгового зала: поставить трансформерпады так, чтобы подтолкнуть покупателя к самостоятельному выбору. Если у трансформерпада цены L слева стоит трансформерпад, стоящий S, а справа - трансформерпад, стоящий F денежных знаков, при этом L < S и L < F, то покупатель почти наверняка выберет тот, что стоит L, не обращаясь к консультанту. И, без сомнения, уйдет довольным.
Распорядитель торгового зала некоторое время пребывал в благоговейном восторге от столь простого и столь мудрого совета, а затем велел срочно переставить товар так, чтобы в ряду устройств обязательно встречалась хотя бы одна тройка трансформерпадов, в которой средний стоил бы дешевле, чем его соседи слева и справа. И действительно, уже к концу дня стало ясно, что такие "средние" трансформерпады продаются намного лучше.
По заданной последовательности ценников Вы должны определить, какой трансформерпад лучше всего продается. Если в последовательности существует несколько троек, удовлетворяющих описанным выше требованиям, выведите цену наиболее дешевого из "средних". Гарантируется, что хотя бы одна такая тройка в последовательности есть.

Формат входного файла input.txt
Первая строка - целое число N (3 <= N <= 600000) - количество трансформерпадов на витрине
Вторая строка - N натуральных чисел через пробел, каждое число не превосходит 100000, - цены трансформерпадов в порядке их расположения на витрине

Формат выходного файла output.txt
Первая строка - целое число - цена трансформерпада, который лучше всего продается

Пример входного файла - 1
3
25020 10870 13040

Пример выходного файла - 1
10870

Пример входного файла - 2
5
10870 25020 13040 19870 14999

Пример выходного файла - 2
13040

Сдать задачу

Задать вопрос жюри по этой задаче