You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

Description

有一座魔能长桥，桥的长度为 $L$。桥上的有效坐标是 $1,2,\dots,L$。

桥上有 $N$ 个精灵，每个精灵每秒向自己面朝的方向移动 1 个单位。

• 走到坐标 $0$ 代表从桥左端离开；
• 走到坐标 $L+1$ 代表从桥右端离开。

当两个精灵相遇时，二者立刻原地转身，朝反方向继续行走，转身不消耗时间。初始保证没有两个精灵处在同一个坐标。多个精灵可以站在同一个坐标上。

你并不知道每个精灵一开始面朝的方向。 请求出部队全部撤离长桥所需要的最少可能时间与最多可能时间。

注意：全部撤离的时间，等于最后一个精灵离开桥所花费的时间。精灵一旦离开桥就不再参与后续碰撞。

Format

Input

第一行一个整数 $L$，表示魔能长桥的长度。桥上的坐标为 $1,2,\dots,L$。 第二行一个整数 $N$，表示初始时留在桥上的精灵数目。 第三行共有 $N$ 个整数，分别表示每个精灵的初始坐标。

Output

共一行，输出 2 个整数，分别表示精灵部队撤离魔能长桥的最小时间和最大时间。两个整数由一个空格隔开。

Sample

Input

4
2
1 3

Output

2 4

Constraint

对于 $100\%$ 的数据，满足初始时没有两个精灵同在一个坐标，$1\le L\le 5\times 10^3$，$0\le N\le 5\times 10^3$，且数据保证 $N\le L$。