В далеком будущем на Земле сутки длятся n часов, и соответственно, есть n часовых поясов. Местное время в соседних часовых поясах различается на час. При записи местного времени для числа часов используются числа от 1 до n, т.е. времени «0 часов» не бывает, вместо этого бывает «n часов». Когда местное время в 1-м часовом поясе 1 час, местное время в i-м часовом поясе i часов.
Некоторая платформа по проведению онлайн-соревнований по программированию хочет провести соревнование длиной в один час, причем так, чтобы начало соревнования совпало бы с началом какого-то часа (во всех часовых зонах). Платформа знает, что из i-го часового пояса в соревновании хотят принять участие ai человек. Каждый человек примет участие, если соревнование начнется не раньше s часов 00 минут местного времени (по часовому поясу этого человека), а закончится — не позже f часов 00 минут местного времени. Величины s и f одинаковы для всех часовых поясов. Если соревнование начинается в f часов 00 минут местного времени люди участвовать в нем не будут.
Помогите онлайн-платформе выбрать такой час, когда наибольшее число людей примут участие в соревновании.
Выходные данные
В единственной строке выведите одно целое число — время начала соревнований по местному времени первого часового пояса, такое, чтобы в нём поучаствовало как можно больше людей. Если ответов несколько, выведите минимальный.
Примечание
В первом примере оптимально начать соревнование в 3 часа по времени первого часового пояса. Тогда во втором часовом поясе будет 1 час, а в третьем — 2 часа. Только один человек из первого часового пояса не примет участия в соревновании.
Во втором примере в соревновании примут участие люди из третьего и четвертого часовых поясов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 3
1 3
|
3
|
|
2
|
5
1 2 3 4 1
1 3
|
4
|