Бесси любит скачивать игры для своего мобильного телефона, хотя ей и кажется, что маленький сенсорный экран довольно неудобен в использовании из-за её больших копыт.
Её особенно заинтересовала игра, в которую она сейчас играет. Игра начинается с последовательности из N положительных целых чисел (2 ≤ N ≤ 262144), каждое из которых находится в диапазоне от 1 до 40. За один ход Бесси может взять два соседних числа с одинаковыми значениями и заменить их на одно число на единицу больше (например, она может заменить две соседние семёрки на восьмёрку). Цель состоит в том, чтобы максимизировать значение наибольшего числа в последовательности в конце игры. Пожалуйста, помогите Бесси набрать как можно больше очков.
Входные данные
Первая строка ввода содержит N, а следующие N строк дают последовательность из N чисел в начале игры.
Выходные данные
Пожалуйста, выведите наибольшее целое число, которое может сгенерировать Бесси.
Примечание
В приведенном здесь примере Бесси сначала объединяет вторую и третью единицы, чтобы получить последовательность 1 2 2, а затем объединяет двойки в тройку. Обратите внимание, что объединение первых двух единиц не является оптимальным.
| № | Входные данные | Выходные данные |
|
1
|
4
1
1
1
2
|
3
|