Garbage containers are installed at every kilometer of the two-way ring road. The length of the ring road is
N kilometers. The zero kilometer and the
Nth kilometer of the road are at the same point. The amount of garbage that accumulates daily in each of the containers is known.
There are two garbage trucks on the road. One goes clockwise, the other against. Both garbage trucks leave the recycling center at the same time towards each other and meet near one of the containers. Only one garbage truck can take out garbage from one container. The garbage delivery time is calculated as the product of the amount of garbage by the distance from the point to the recycling center. The waste recycling center was opened in one of the garbage collection points in such a way that the total time for garbage collection by two garbage trucks was minimal.
Determine which container number you need to place a recycling center in order to minimize the time for garbage trucks to collect garbage.
Input
The first line of the input contains number
N (1 <=
N <= 10,000,000) – the number of garbage collection points on the ring road. Each of the following
N lines contains a number of – the amount of garbage in the container (all numbers are natural, the amount of garbage in each point does not exceed 1000). The numbers are given in order of containers on the motorway, starting from the first kilometer.
Imprint
Display one number on the screen - the answer to the problem.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
7
8
20
5
13
7
19
21 |
7 |
With such initial data, it is necessary to open a recycling center near container number 7:
The first garbage truck collects garbage: 0 * 21 + 1 * 19 + 2 * 7 + 3 * 13 = 72
The second garbage truck will spend time: 0 * 21 + 8 * 1 + 20 * 2 + 3 * 5 = 63
Total time spent by two garbage trucks: 72 |