29304번 - Вирусы 다국어

Пока доктору Хаусу снится страшный сон об эпидемии, его бывший подчиненный Эрик Форман совершает прорыв в науке! Сейчас он занимается изучением воздействия вирусов на различный типы тканей.

Форман уже выяснил, что ткань может быть представлена как последовательность клеток, каждая из которых характеризуется своей резистентностью. Каждый вирус можно охарактеризовать одним натуральным числом $K$ --- его заразностью.

У вируса с заразностью $K$, попавшего в какую-то клетку, есть три последовательных стадии жизни: инкубация, распространение и существование. Вирус в ткани живет по следующим правилам:

• изначально он находится только в клетке с номером один в стадии распространения
• в стадии инкубации и существования вирус спокойно поглощает свою клетку и никак не влияет на все остальные
• стадия инкубации вируса в клетке номер $i$ переходит в стадию распространения ровно в тот момент, когда стадия распространения в клетке номер $i - 1$ заканчивается и переходит в стадию существования
• в стадии распространения вирус нападает на $K$ клеток с наименьшими номерами, в которых вируса еще нет. Если резистентность какой-то из этих $k$ клеток больше, чем резистентность клетки, из которой вирус распространяется, то вся ткань вырабатывает иммунитет, и вирус ее покидает. В противном же случае вирус поселяется в этих клетках и в них начинается стадия инкубации
• в случае успешного заражения $K$ клеток, стадия распространения заканчивается и начинается в следующей клетке

Понятно, что каждая ткань будет заражена далеко не всеми вирусами. Сейчас же Форман хочет ответить на вопрос: какова минимальная заразность вируса, который, попав в изучаемую ткань, сможет полностью ее захватить.

В первой строке дано целое число $N$ ($1 < N \le 5{\,}000$) --- количество клеток в ткани. Во второй строке дано $N$ целых чисел $a_i$ ($1 \le a_i \le 10^9$), обозначающих резистентности клеток ткани.

В первой строке выведите единственное число $K$ --- минимальную заразность вируса, способного поглотить исследуемую ткань полностью. Если же такого вируса не существует --- выведите 0.