Задача "Квас" (окружная олимпиада по информатике 2007)

На тропическом острове в разгар туристического сезона особой популярностью пользуется квас. Раньше весь квас импортировался из России, но с увеличением популярности этого напитка встал вопрос о производстве кваса прямо на месте. На острове расположено 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 тугриков.