Хотя Блейк и является начальником Криса, это никак не мешает их дружбе. Обычно по вечерам они собираются вместе в баре и обсуждают там увлекательные задачи, в которых требуется максимизировать какую-нибудь величину. В этот раз им попалась особенная задача...
Пусть дан массив a длины n. Назовём характеристикой массива число 
— сумму произведений i-го числа в массиве a на число i. Разрешается ровно один раз сделать следующую операцию: выбрать некоторый элемент массива и переставить его в любое место в массиве. В частности, разрешается переставить элемент в начало, в конец или поставить его обратно на ту же позицию. Необходимо получить массив с максимально возможным значением характеристики.
Выходные данные
Выведите единственное целое число — максимально возможное значение характеристики массива a, если можно переставить ровно один элемент.
Примечание
В первом примере можно удалить первый элемент из массива и вставить его перед третьим (перед числом 5), таким образом получив максимальный ответ: 3·1 + 2·2 + 4·3 + 5·4 = 39.
Во втором примере максимальный ответ можно получить, удалив пятый элемент из массива и вставив его перед третьим: 1·1 + 1·2 + 1·3 + 2·4 + 7·5 = 49.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4 3 2 5
|
39
|
|
2
|
5
1 1 2 7 1
|
49
|
|
3
|
3
1 1 2
|
9
|