Вы - маг, который хочет собирать магическую энергию из домов вдоль улицы. Дома на этой улице расположены по кругу. Это означает, что первый дом является соседом последнего. В каждом доме сосредоточена определенная магическая энергия, и единственным ограничением является то, что если вы извлекаете магическую энергию из двух соседних домов в одну и ту же ночь, то это вызывает негативные последствия для вас и окружающей среды.
Зная уровень магической энергии в каждом доме, найдите максимальное количество магической энергии, которое вы можете собрать сегодня, избегая извлечения энергии из соседних домов в одну и ту же ночь.
Входные данные
В первой строке записано число n - количество домой вдоль улицы. Во второй строке - n целых чисел ai - количество магической энергии в i-м доме.
Ограничения на входные данные
1 <= n <= 1000 <= a[i] <= 10001 <= i <= n
Выходные данные
Выведите максимальное количество магической энергии, которую вы сможете собрать.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
2 3 2 |
3 |
| 2 |
4
1 2 3 1 |
4 |
| 3 |
3
1 2 3 |
3 |