Sonya Partymaker
Contest: Codeforces Round 371 (Div. 1)
Difficulty rating: 3300
Tags: binary search, dp

Owl Sonya decided to become a partymaker. To train for this role she gather all her owl friends in the country house. There are m chairs located in a circle and consequently numbered with integers from 1 to m. Thus, chairs i and i + 1 are neighbouring for all i from 1 to m - 1. Chairs 1 and m are also neighbouring. Some chairs are occupied by her friends. There are n friends in total. No two friends occupy the same chair. Rules are the following:

1. Each participant removes from the game the chair he is currently sitting on.
2. Each of the participants choose a direction that she will follow: clockwise (indices increase, from m goes to 1) and counter-clockwise (indices decrease, from 1 goes to m). This direction may coincide or be different for any pair of owls.
3. Each turn all guests move one step in the chosen directions. If some guest move to the position with a chair there, he removes this chair from the game.
4. Game ends if there are no more chairs left in the game.

Owls are very busy and want to get rid of the game as soon as possible. They cooperate to pick the direction. Your goal is to find the minimum number o moves required to finish the game.

Input format:
The first line of the input contains a single integer m (1 ≤ m ≤ 109) — the length of the circle.

The second line contains a single integer n (1 ≤ n ≤ 100 000) — the number of friends.

Last line contains an increasing sequence of n integers ai (1 ≤ ai ≤ m) — initial positions of all owls.

Output format:
Print the minimum number of move required to finish the game. Note, that 0 also may be an answer.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
In the first sample, it's possible if all owls will move clockwise, i.e. in the direction of increasing indices.

In the sample, first owl has to move clockwise, while the second — counterclockwise.

In the third sample, the first and the fourth owls should move counterclockwise, while the third and the sixth — clockwise. The second and the firth may move in any direction.

Example input:
6
3
1 3 5

Example output:
1

Example input:
6
2
1 6

Example output:
2

Editorial:
Will use binary search to find the answer. Assume that we need to know if it is enough x minutes to visit each vertex. Lets dp[i][0...1] is equal to minimum number of vertices to the left of i, which wasn't visited yet, second parameter is equal to 1, if we have't launched robot from vertex i. I.e. when dp[i][j] > 0 vertices [i−dp[i][j], i−1] haven't been visited, and if dp[i][j] < 0 then dp[i][j] vertices to the right we still can visit. We need to calculate such DP for two starting states (dp[0][0] = 0, dp[0][1] = 0). Now we need to implement next:
• if 0 < dp[i][1] ≤ x then distance can be walked and we need to update dp[i][0] by 0
• if dp[i][1] ≤ 0 then we can update dp[i][0] by −x
• using dp[i][0], update dp[i + 1][1]
• using dp[i][1], update dp[i + 1][0]
Walk in time x is also possible if dp[n][0..1 (depending on start state)]  ≤ 0. Need to assume few other facts:
if dp[n][j] ≠ 0 then we can repeat DP with param dp[0][j] = dp[n][j], and if, dp[n][j] ≤ dp[0][j], then distance can be walked
To assume every case we need to calculate this DP for each pair of sequent vertices