Вокруг города проходит двухсторонняя кольцевая автомобильная дорога длины $$$L$$$. Одна из точек дороги выбрана в качестве начальной (нулевая координата).
Вдоль дороги расположены $$$N$$$ заправок. Их владелец хочет построить хранилище топлива возле одной из заправок так, чтобы сумма расстояний от хранилища до оставшихся заправок была минимальной. Найдите оптимальное место расположения хранилища.
В первой строке входных данных содержится целое число $$$L$$$ ($$$1 \le L \le 10^9$$$) — длина дороги.
Во второй строке содержится целое число $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$) — количество заправок.
В следующих $$$N$$$ строках записаны $$$N$$$ несовпадающих целых чисел $$$x_1$$$, $$$x_2$$$, ..., $$$x_N$$$ в возрастающем порядке, где $$$x_i$$$ — это координата $$$i$$$-й заправки, то есть длина пути от начальной точки до $$$i$$$-й заправки, если двигаться по часовой стрелке ($$$0 \le x_i \lt L$$$).
Выведите одно целое число от 1 до $$$N$$$ — номер заправки, возле которой нужно построить хранилище. Если есть несколько верных ответов, выведите любой.
Подзадача 1 (до 40 баллов): $$$L \le 1000$$$, $$$N \le 1000$$$.
Подзадача 2 (до 60 баллов): нет дополнительных ограничений.
83145
2
Рисунок к примеру:
Обратите внимание, что сумма расстояний может не поместиться в 32-битный тип данных. Рекомендуется использовать 64-битный тип данных, например, тип long long в языке C++, тип int64 в языке Pascal, тип long в языках Java и C#. Язык Python автоматически работает с целыми числами любой длины.
