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

Даны n чисел — ценности в домах по кругу. Требуется выбрать набор домов с максимальной суммарной ценностью так, чтобы никакие два выбранных дома не были соседними.

Входные данные

В первой строке задано число n — количество домов.

Во второй строке заданы n целых чисел a_i — ценности в домах.

Выходные данные

Выведите одно число — максимальную суммарную ценность, которую может собрать сборщик.

Ответ может не помещаться в 32-битный тип.

Ограничения

• 1 <= n <= 2 * 10^5
• 0 <= a_i <= 10^9

Примеры

Пример 1

Входные данные

3
2 3 2

Выходные данные

3

Пояснение

Первый и третий элементы соседи по кругу, поэтому лучший выбор — один элемент 3.

Пример 2

Входные данные

1
0

Выходные данные

0

Пример 3

Входные данные

2
1 1000000000

Выходные данные

1000000000