На тропическом острове в разгар туристического сезона особой популярностью пользуется квас. Раньше весь квас импортировался из России, но с увеличением популярности этого напитка встал вопрос о производстве кваса прямо на месте. На острове расположено N курортных городов, все города расположены на побережье. Вдоль побережья проходит единственная на острове кольцевая дорога, соединяющая все города. Движение по дороге возможно в любом направлении. Для каждого города известно, сколько бочек кваса требуется ему ежедневно.
Планируется построить всего один завод в каком-нибудь городе, и развозить продукцию по остальным городам. Перевозка одной бочки в соседний город стоит один тугрик (местная валюта).
Ваша задача состоит в том, чтобы определить, в каком из городов следует построить завод, чтобы минимизировать транспортные расходы.
Формат входных данных. Первая строка входных данных содержит число N - количество городов ( N ≤ 10) и еще N чисел - количество кваса, требуемое ежедневно 1-м, 2-м, ..., N-м городом (города нумеруются подряд вдоль кольцевой дороги).
Формат выходных данных. Выведите одно число - номер города, в котором следует построить завод. Если подходящих городов окажется несколько - выведите номер любого из них.
| Пример ввода | Пример вывода |
3 5 3 10 |
3 |
6 4 4 1 5 1 3 |
2 |
Пояснение для второго примера (см. рисунок): На острове 6 городов, потребность каждого города указана в кружочках, номер города рядом с кружочком. Если построить завод во 2-м городе (он выделен серым), то потребуется заплатить 4 + 1 (стоимость перевозки в 1-й и 3-й города) + 5*2 + 3*2 (в 4-й и 6-й) + 1*3 (в 5-й см. рисунок). Во 2-й вообще ничего не везем. Это будет 24 тугрика. Легко проверить, что если построить завод в других городах, сумма будет больше. Например, если построить в 4-м городе, то сумма составит 1 + 1 + 3*2 + 4*2 + 4*3 = 28 тугриков.