У Вики есть n банок с красками различных цветов. Все банки пронумерованы от 1 до n, при этом в i-й банке содержится ai литров краски цвета i.
Также у Вики есть бесконечно длинный прямоугольный лист бумаги шириной 1, состоящий из квадратов размера 1 × 1, пронумерованных 1, 2, 3 и так далее до бесконечности. Вика решила, что будет закрашивать квадраты один за другим слева направо, начиная с квадрата номер 1 и некоторого цвета, при этом если предыдущий квадрат был закрашен в цвет x, то следующий квадрат она будет красить в цвет x + 1. Если же x = n, то Вика красит следующий квадрат цветом номер 1. Если цвет, которым Вика собирается красить очередной квадрат, уже кончился, то Вика останавливается и больше ничего не красит.
Один квадрат всегда полностью красится в один цвет, и на это уходит ровно 1 литр краски. Перед вами стоит задача посчитать максимально возможное количество закрашенных квадратов, если Вика правильно выберет цвет для покраски квадрата с номером 1.
Выходные данные
Выходные данные должны содержать единственное целое число — максимальное количесто квадратов размера 1 × 1, которые могут быть покрашены Викой, если она действует по описанным выше правилам.
Примечание
В первом примере выгоднее всего начинать красить с цвета номер 4. Тогда квадраты, начиная с левого, будут раскрашены в цвета: 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5.
Во втором примере можно начинать красить с любого цвета.
В третьем примере выгоднее всего начинать красить с цвета номер 5.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 4 2 3 3
|
12
|
|
2
|
3
5 5 5
|
15
|
|
3
|
6
10 10 10 1 10 10
|
11
|