1906: 命运之桥

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:35 解决:15

题目描述

有一座名为“命运之桥”的独木桥,它横跨在一条深不见底的峡谷之上,连接着王国的两个重要领地。你,作为一位智慧而勇敢的探险家,正带领着一群旅人,踏上了一段寻找古老宝藏的冒险之旅。旅途漫长而艰辛,旅人们站在桥上欣赏四周壮丽的风光。然而,这座桥异常狭窄,每次只能允许一个人通过,且一旦有两人迎面相遇,他们则无法绕行,只能有一个人退回到起点,让另一个人先行。但是,可以有多个人同时呆在同一个位置。

这时来了一群强盗,你们需要赶紧离开桥,桥的长度为 L旅人们只能呆在坐标为整数的地方。所有旅人的速度都为 1,但一个旅人某一时刻来到了坐标为 0 L+1 的位置,他就离开了桥。但问题在于,你对每位旅人的初始行进方向一无所知,他们有的可能正向桥的另一端前进,有的可能正打算返回。但是旅人都有一个初始方向,他们会以匀速朝着这个方向行走,中途不会自己改变方向。但是,如果两个旅人面对面相遇,他们无法彼此通过对方,于是就分别转身,继续行走。转身不需要任何的时间。

你急需计算出,你们全部撤离这座独木桥需要的最大时间,以及最小时间。

输入

第一行共一个整数 L,表示桥的长度。桥上的坐标为 L1L2......L

第二行共一个整数 N,表示初始时留在桥上的旅人数目。

第三行共有 N 个整数,分别表示每个旅人的初始坐标。

输出

共一行,输出 2 个整数,分别表示旅人撤离独木桥的最大时间和最小时间。2个整数由一个空格符分开。

样例输入 复制

4
2
1 3

样例输出 复制

4 2

提示

对于 lns="http://www.w3.org/1998/Math/MathML">100% 的数据,满足初始时,没有两个旅人同在一个坐标,lns="http://www.w3.org/1998/Math/MathML">1L5×103lns="http://www.w3.org/1998/Math/MathML">0N5×103,且数据保证 lns="http://www.w3.org/1998/Math/MathML">NL