Quickest Escape from the Balancing Bridge

A group of n people are on a narrow, unstable wooden bridge of length \(L\) meters. Each person moves at a constant speed of 1 meter per second. A person can exit the bridge as soon as they reach either endpoint. However, because the bridge is so narrow that only one person can occupy it at a time, if two people meet, they cannot pass through each other and must reverse direction immediately.

Initially, the \(i\)-th person is at a distance \(a_i\) meters from the left end of the bridge. Although their initial direction is unknown, they are allowed to switch directions at any time. This enables each person to choose the optimal path to leave the bridge as quickly as possible.

It can be shown that the minimum time required for all individuals to exit the bridge is:

\[ T = \max_{1\le i \le n} \min(a_i, L - a_i) \]

In other words, each person can plan to head towards the nearer end. The answer is the maximum among these minimum exit times.

inputFormat

The first line contains two integers \(L\) and \(n\), representing the length of the bridge and the number of people, respectively.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\), where \(a_i\) is the distance from the left end to the \(i\)-th person.

outputFormat

Output a single integer representing the minimum time (in seconds) required for all people to exit the bridge.

sample

10 3
2 6 7

4