P1007 Single-Plank Bridge

战争已经进入到紧要时间。你是运输小队长，正在率领运输部队向前线运送物资。运输任务像做题一样的无聊。你希望找些刺激，于是命令你的士兵们到前方的一座独木桥上欣赏风景，而你留在桥下欣赏士兵们。士兵们十分愤怒，因为这座独木桥十分狭窄，只能容纳 $1$ 个人通过。假如有 $2$ 个人相向而行在桥上相遇，那么他们 $2$ 个人将无法绕过对方，只能有 $1$ 个人回头下桥，让另一个人先通过。但是，可以有多个人同时呆在同一个位置。

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.

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 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.

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