Evacuation of the Bridge

Suddenly, you receive an urgent message from command: enemy bombers are headed toward the single-plank bridge you and your troops occupy! For safety, your soldiers must evacuate the bridge. The bridge has a length \( L \) and soldiers can only stand on integer coordinates from 1 to \( L \). All soldiers move at a speed of 1 unit per time unit. However, if at any moment a soldier reaches coordinate 0 or \( L+1 \), he immediately leaves the bridge.

Each soldier has an initial facing direction and will proceed in that direction without changing it on their own. If two soldiers meet head‐on they cannot pass each other, so they both instantly turn around and continue walking (turning takes no time).

You have lost control of your troops, and even the initial directions of each soldier are unknown. Therefore, you want to determine two times:

• The minimum time after which it is possible for all soldiers to have evacuated the bridge, if the initial directions turn out to be the most favorable.
• The maximum time that might be required for all soldiers to evacuate the bridge, if the initial directions are chosen in the worst possible way.

It turns out that the problem can be modeled by noting that when two soldiers meet and turn around, it is equivalent to them passing through each other. Thus, the evacuation times depend solely on the distances from each soldier to the two exits. Specifically, for a soldier at position \( x \):

• The distance to the left exit is \( x \).
• The distance to the right exit is \( L+1-x \).

Thus, if we denote the soldiers' positions as \( x_1, x_2, \dots, x_N \), then the answers are given by:

\( t_{min} = \max_{1 \le i \le N} \min(x_i, L+1-x_i) \)

\( t_{max} = \max_{1 \le i \le N} \max(x_i, L+1-x_i) \)

Your task is to compute these two values.

inputFormat

The first line of input contains two integers \( L \) and \( N \) (\( 1 \le L \le 10^9 \), \( 1 \le N \le 10^5 \)), representing the length of the bridge and the number of soldiers, respectively. The second line contains \( N \) integers denoting the positions \( x_i \) (\( 1 \le x_i \le L \)) of each soldier.

outputFormat

Output two integers separated by a space: the minimum and the maximum time required for all soldiers to evacuate the bridge, as defined above.

sample

5 3
2 1 5

2 5