Description

Suddenly, you receive a message from headquarters: enemy bombers are flying toward the single-plank bridge where you are located. For safety, your unit must evacuate the bridge. The bridge has length $L$, and soldiers can only stay at positions with integer coordinates. All soldiers move at speed $1$, and once a soldier reaches coordinate $0$ or $L+1$ at any moment, he leaves the bridge.

Each soldier has an initial facing direction and will walk uniformly in that direction without changing it on his own. However, if two soldiers meet face to face, they cannot pass through each other, so they both turn around and keep walking. Turning around takes no time.

Due to earlier anger, you can no longer control your soldiers. You do not even know each soldier’s initial facing direction. Therefore, you want to know the minimum possible time for your unit to completely evacuate the bridge. In addition, as headquarters is arranging to block the enemy’s advance, you also need to know the maximum possible time for your unit to completely evacuate the bridge.

Input Format

The first line contains a single integer $L$, the length of the bridge. The coordinates on the bridge are $1, 2, \cdots, L$.

The second line contains a single integer $N$, the number of soldiers initially on the bridge.

The third line contains $N$ integers, the initial coordinate of each soldier.

Output Format

Output a single line with $2$ integers: the minimum and maximum time for the unit to evacuate the bridge. The $2$ integers are separated by a space.

4
2
1 3

2 4

Hint

For $100\%$ of the testdata, initially no two soldiers occupy the same coordinate, $1 \le L \le 5 \times 10^3$, $0 \le N \le 5 \times 10^3$, and the data guarantees $N \le L$.

Translated by ChatGPT 5