OJ现已增加邮箱找回密码功能,还没有绑定邮箱的同学们请抓紧时间,以免密码丢失无法找回


问题 G: 碰到就掉头

问题 G: 碰到就掉头

时间限制: 1 Sec  内存限制: 128 MB
提交: 25  解决: 18
[提交] [状态] [讨论版] [命题人:]

题目描述

有那么一个长度为L的独木桥,现在你在空中看到了许多只蚂蚁正在桥上,他们有的向右走,有的向左走,并且速度都为1个单位每秒,但是当两只不同方向的蚂蚁相撞时,他们就会互相掉头(即向左的走的蚂蚁会在该位置向右走,向右走的同理,掉头所需要的时间忽略不计)。当蚂蚁走到桥的两端即0L+1时,他们就会掉下去。现在给出你蚂蚁在桥上的位置,但是你并不知道他们最初的方向,你能计算出所有蚂蚁全部掉下的最小时间和最大时间吗?注意可能多只蚂蚁在同一个位置,你可以认为他们是同一个方向。

输入

第一行输入一个正整数L表示独木桥的长度(1 ≤ L ≤ 5000)。
第二行输入一个正整数n表示蚂蚁的个数(1 ≤ n ≤ 100000)。
接下来一行一共n个小于等于L的正整数,相邻数字用空格隔开表示每只蚂蚁的位置。

输出

所有蚂蚁全部掉下的最小时间和最大时间。

样例输入 Copy

9
3
1 3 4

样例输出 Copy

4 9