F. Два плаката
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Вы хотите прорекламировать свой новый бизнес, поэтому собираетесь разместить два плаката на рекламном щите в центре города. Рекламный щит состоит из $$$n$$$ вертикальных панелей шириной $$$1$$$ и различной целочисленной высоты, соединенных горизонтальной перекладиной. $$$i$$$-я из $$$n$$$ панелей имеет высоту $$$h_i$$$.

Изначально все панели свисают с перекладины (их верхние края лежат на ней), но перед размещением двух постеров разрешается сдвинуть каждую панель вверх на любую целую величину, главное, чтобы она все еще была соединена с перекладиной (нижний край панели лежит под или на ней).

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

Какую максимальную общую площадь могут покрыть два плаката, если вы сделаете оптимальные операции? Заметьте, что вы также можете разместить плакат площади $$$0$$$. Этот случай равносилен размещению одного плаката.

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

Первая строка входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^4$$$) — количество вертикальных панелей.

Вторая строка входных данных содержит $$$n$$$ целых чисел $$$h_1, h_2, ..., h_n$$$ ($$$1 \le h_i \le 10^{12}$$$) — высоты $$$n$$$ вертикальных панелей.

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

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

Примеры
Входные данные
6
2 2 3 5 4 5
Выходные данные
18
Входные данные
1
1
Выходные данные
1
Примечание

В первом тестовом примере мы можем выбрать верхний плакат с площадью $$$12$$$ и нижний плакат с площадью $$$6$$$, как на изображении ниже.

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