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