E. Торт
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Катя решила приготовить торт из коржей. У нее есть $$$n$$$ типов коржей, при этом про $$$i$$$-й тип известно целое число $$$a_i$$$ — количество коржей этого типа, которые есть у Кати.

Катя будет выкладывать коржи один на другой, при этом она не хочет, чтобы два коржа одного типа шли подряд в ее торте. Начинать выкладывать коржи Катя может с любого типа.

Определите максимальное количество коржей, которые Катя может использовать для приготовления своего торта.

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

В первой строке следует целое число $$$n$$$ $$$(1 \le n \le 200\,000)$$$ — количество типов коржей, которые есть у Кати.

Во второй строке следует последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^{12})$$$, где $$$a_i$$$ равно количеству коржей $$$i$$$-го типа, которые есть у Кати.

Следует обратить внимание, что входные данные в этой задаче не помещаются в стандартный $$$32$$$-битный тип данных. Необходимо использовать $$$64$$$-битный тип данных (long long в С++, int64 в Паскале, long в Java).

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

Выведите максимальное количество коржей, которые Катя может использовать для приготовления своего торта.

Примеры
Входные данные
3
3 1 3
Выходные данные
7
Входные данные
5
1 10 1 1 1
Выходные данные
9
Входные данные
2
1000000000000 1000000000000
Выходные данные
2000000000000
Примечание

В первом примере Катя сможет использовать все коржи, которые у неё есть, для приготовления торта. Например, она может их класть в следующем порядке:

  1. корж $$$2$$$-го типа,
  2. корж $$$1$$$-го типа,
  3. корж $$$3$$$-го типа,
  4. корж $$$1$$$-го типа,
  5. корж $$$3$$$-го типа,
  6. корж $$$1$$$-го типа,
  7. корж $$$3$$$-го типа.

Во втором примере Катя сможет использовать $$$9$$$ коржей для приготовления торта. Например, она может их класть в следующем порядке:

  1. корж $$$2$$$-го типа,
  2. корж $$$3$$$-го типа,
  3. корж $$$2$$$-го типа,
  4. корж $$$5$$$-го типа,
  5. корж $$$2$$$-го типа,
  6. корж $$$4$$$-го типа,
  7. корж $$$2$$$-го типа,
  8. корж $$$1$$$-го типа,
  9. корж $$$2$$$-го типа.