There is a two-way circular road around the city with a length of $$$L$$$. One point on the road is chosen as the starting point (zero coordinate).
Along the road, there are $$$N$$$ fuel stations. The owner wants to build a fuel storage facility near one of the stations in such a way that the sum of the distances from the storage to the remaining stations is minimized. Find the optimal location for the storage facility.
The first line of the input contains an integer $$$L$$$ ($$$1 \le L \le 10^9$$$) — the length of the road.
The second line contains an integer $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$) — the number of fuel stations.
In the following $$$N$$$ lines, there are $$$N$$$ distinct integers $$$x_1$$$, $$$x_2$$$, ..., $$$x_N$$$ in increasing order, where $$$x_i$$$ is the coordinate of the $$$i$$$-th station, i.e. the distance from the starting point to the $$$i$$$-th station when moving clockwise ($$$0 \le x_i \lt L$$$).
Output a single integer from 1 to $$$N$$$ — the number of the fuel station near which the storage facility should be built. If there are multiple correct answers, output any.
Subtask 1 (up to 40 points): $$$L \le 1000$$$, $$$N \le 1000$$$.
Subtask 2 (up to 60 points): no additional constraints.
83145
2
Illustration for the example:
Note that the sum of distances may not fit into a 32-bit data type. It is recommended to use a 64-bit data type, such as the long long type in C++, the int64 type in Pascal, or the long type in Java and C#. Python automatically handles integers of any length.
