題目背景

戰(zhàn)爭(zhēng)已經(jīng)進(jìn)入到緊要時(shí)間。你是運(yùn)輸小隊(duì)長，正在率領(lǐng)運(yùn)輸部隊(duì)向前線運(yùn)送物資。運(yùn)輸任務(wù)像做題一樣的無聊。你希望找些刺激，于是命令你的士兵們到前方的一座獨(dú)木橋上欣賞風(fēng)景，而你留在橋下欣賞士兵們。士兵們十分憤怒，因?yàn)檫@座獨(dú)木橋十分狹窄，只能容納一個(gè)人通過。假如有兩個(gè)人相向而行在橋上相遇，那么他們兩個(gè)人將無妨繞過對(duì)方，只能有一個(gè)人回頭下橋，讓另一個(gè)人先通過。但是，可以有多個(gè)人同時(shí)呆在同一個(gè)位置。

題目描述

突然，你收到從指揮部發(fā)來的信息，敵軍的轟炸機(jī)正朝著你所在的獨(dú)木橋飛來！為了安全，你的部隊(duì)必須撤下獨(dú)木橋。獨(dú)木橋的長度為L，士兵們只能呆在坐標(biāo)為整數(shù)的地方。所有士兵的速度都為1，但一個(gè)士兵某一時(shí)刻來到了坐標(biāo)為0或L+1的位置，他就離開了獨(dú)木橋。 每個(gè)士兵都有一個(gè)初始面對(duì)的方向，他們會(huì)以勻速朝著這個(gè)方向行走，中途不會(huì)自己改變方向。但是，如果兩個(gè)士兵面對(duì)面相遇，他們無法彼此通過對(duì)方，于是就分別轉(zhuǎn)身，繼續(xù)行走。轉(zhuǎn)身不需要任何的時(shí)間。 由于先前的憤怒，你已不能控制你的士兵。甚至，你連每個(gè)士兵初始面對(duì)的方向都不知道。因此，你想要知道你的部隊(duì)最少需要多少時(shí)間就可能全部撤離獨(dú)木橋。另外，總部也在安排阻攔敵人的進(jìn)攻，因此你還需要知道你的部隊(duì)最多需要多少時(shí)間才能全部撤離獨(dú)木橋。

輸入輸出格式

輸入格式：

第一行：一個(gè)整數(shù)L，表示獨(dú)木橋的長度。橋上的坐標(biāo)為1…L 第二行：一個(gè)整數(shù)N，表示初始時(shí)留在橋上的士兵數(shù)目 第三行：有N個(gè)整數(shù)，分別表示每個(gè)士兵的初始坐標(biāo)。

輸出格式：

只有一行，輸出兩個(gè)整數(shù)，分別表示部隊(duì)撤離獨(dú)木橋的最小時(shí)間和最大時(shí)間。兩個(gè)整數(shù)由一個(gè)空格符分開。

輸入輸出樣例

輸入樣例#1：

4 2 1 3

輸出樣例#1：

2 4

說明

初始時(shí)，沒有兩個(gè)士兵同在一個(gè)坐標(biāo)。 數(shù)據(jù)范圍N<=L<=1000。

Analysis

是在下輸了 最短的情況不難想到左邊的人全部向左，右邊的人全部向右，然后找最大值 最久的久比較神奇了 首先每個(gè)士兵都有相等的速度，沒有分別，也就是可以彼此替換 那么相向的兩士兵折返其實(shí)可以看作代替對(duì)方直走了 也就是說在左邊的向右走，右邊的人向左走的最大值 不得不服

Code