Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

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

У Вики есть n банок с красками различных цветов. Все банки пронумерованы от 1 до n, при этом в i-й банке содержится ai литров краски цвета i.

Также у Вики есть бесконечно длинный прямоугольный лист бумаги шириной 1, состоящий из квадратов размера 1 × 1, пронумерованных 1, 2, 3 и так далее до бесконечности. Вика решила, что будет закрашивать квадраты один за другим слева направо, начиная с квадрата номер 1 и некоторого цвета, при этом если предыдущий квадрат был закрашен в цвет x, то следующий квадрат она будет красить в цвет x + 1. Если же x = n, то Вика красит следующий квадрат цветом номер 1. Если цвет, которым Вика собирается красить очередной квадрат, уже кончился, то Вика останавливается и больше ничего не красит.

Один квадрат всегда полностью красится в один цвет, и на это уходит ровно 1 литр краски. Перед вами стоит задача посчитать максимально возможное количество закрашенных квадратов, если Вика правильно выберет цвет для покраски квадрата с номером 1.

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

В первой строке входных данных записано целое положительное число n (1 ≤ n ≤ 200 000) — количество баночек с красками различных цветов, которые есть у Вики.

Во второй строке входных данных следует последовательность целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109), где ai равно количеству литров краски с цветом i, которые есть у Вики.

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

Выходные данные должны содержать единственное целое число — максимальное количесто квадратов размера 1 × 1, которые могут быть покрашены Викой, если она действует по описанным выше правилам.

Примеры
Входные данные
5
2 4 2 3 3
Выходные данные
12
Входные данные
3
5 5 5
Выходные данные
15
Входные данные
6
10 10 10 1 10 10
Выходные данные
11
Примечание

В первом примере выгоднее всего начинать красить с цвета номер 4. Тогда квадраты, начиная с левого, будут раскрашены в цвета: 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5.

Во втором примере можно начинать красить с любого цвета.

В третьем примере выгоднее всего начинать красить с цвета номер 5.