Description

夕受博士的委托，制作了许许多多的“小自在”来帮忙巡视一个重要通道。这个通道十分狭隘，只能允许1个“小自在”通过。即如果两个“小自在”相向而行在桥上相遇，那么它们将无法绕过对方，只能有1个“小自在”回头下桥，让另一个人先通过。但是，可以有多个人同时呆在同一个位置。

可是突然，博士收到消息，敌人将要炸毁这个通道，于是让夕把所有的“小自在”从通道中撤出。通道长度为L，“小自在”只待在坐标为整数的地方，并且速度都为1。如果“小自在”来到了0或者L+1处，就离开了通道。

每个“小自在”都有一个初始面对方向，“小自在”会匀速沿着该方向前进，除非两个“小自在”面对面相遇。由于它们不能绕过对方，它们就会分别转身，继续行走。

由于通道是封闭的，博士不知道每个“小自在”的方向，也不能控制“小自在”。因此，博士需要你帮忙计算所有“小自在”最短以及最长的撤离时间。以方便进行下一步计划。

Input Format

第一行，一个整数L，表示通道长度。L<=50000

第二行，一个整数N，表示“小自在”的数量。N<=50000

第三行，N个整数，表示“小自在”的起始位置。

Output Format

一行两个整数，分别表示最短时间和最长时间。

4
2
1 3

2 4