Задача
На каждом километре кольцевой автодороги с двусторонним движением установлены контейнеры для мусора. Длина кольцевой автодороги равна
N километров. Нулевой километр и
N-й километр автодороги находятся в одной точке. Известно количество мусора, которое накапливается ежедневно в каждом из контейнеров.
На автодороге работают два мусоровоза. Один едет по часовой стрелке, другой против. Оба мусоровоза выезжают из центра переработки одновременно навстречу друг другу и встречаются возле одного из контейнеров. Из одного контейнера вывезти мусор может только один мусоровоз. Время доставки мусора вычисляется как произведение количества мусора на расстояние от пункта до центра переработки. Центр переработки отходов открыли в одном из пунктов сбора мусора таким образом, чтобы общее время сбора мусора двумя мусоровозами было минимально.
Определите, возле контейнера с каким номером необходимо поставить центр переработки, чтобы потребовалось минимальное время мусоровозам для сбора мусора.
Входные данные
Первая строка входных данных содержит число
N (1 <=
N <= 10 000 000) – количество пунктов сбора мусора на кольцевой автодороге. В каждой из следующих
N строк находится число – количество мусора в контейнере (все числа натуральные, количество мусора в каждом пункте не превышает 1000). Числа указаны в порядке расположения контейнеров на автомагистрали, начиная с первого километра.
Выходные данные
Выведите на экран одно число - ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
7
8
20
5
13
7
19
21 |
7 |
При таких исходных данных необходимо открыть центр переработки возле контейнера с номером 7:
Первый мусоровоз собирает мусор: 0 * 21 + 1 * 19 + 2 * 7 + 3 * 13 = 72
Второй мусоровоз потратит времени: 0 * 21 + 8 * 1 + 20 * 2 + 3 * 5 = 63
Итоговое время, которое потратят два мусоровоза: 72 |