On a tropical island, kvass is especially popular at the height of the tourist season. Previously, all kvass was imported from Russia, but with the increasing popularity of this drink, the question arose of producing kvass right on the spot. There are N resort towns on the island, all towns are located on the coast. The only ring road on the island runs along the coast, connecting all the cities. Driving on the road is possible in any direction. Each city knows how many barrels of kvass it needs daily.
It is planned to build only one plant in any city, and deliver products to other cities. Transportation of one barrel to a neighboring city costs one tugrik (local currency).
Your task is to determine in which city the factory should be built in order to minimize transport costs.
Input
The first line of the input contains the number N – number of cities (N ≤ 10) and N numbers – the amount of kvass required daily by the 1st, 2nd, …, Nth city (the cities are numbered consecutively along the ring road).
Imprint
Print one number – the number of the city in which the factory should be built. If there are several suitable cities – print the number of any of them.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
3 5 3 10 |
3 |
|
| 2 |
6 4 4 1 5 1 3 |
2 |
There are 6 cities on the island, the need for each city is indicated in circles, the city number is next to the circle.
If you build a plant in the 2nd city (it is grayed out), you will need to pay 4 + 1 (the cost of transportation to the 1st and 3rd cities) + 5*2 + 3*2 (to the 4th and 6th ) + 1*3 (in the 5th, see the picture).
In the 2nd we do not carry anything at all. It will be 24 tugriks. It is easy to check that if you build a plant in other cities, the amount will be higher. For example, if you build in the 4th city, then the sum will be 1 + 1 + 3*2 + 4*2 + 4*3 = 28 tugriks. |