哦,新年。是时候聚集所有朋友,回顾过去一年发生的感人事件了……
$$$n$$$ 朋友住在一个可以用数轴表示的城市。第 $$$i$$$ 个朋友住在一座坐标为整数 $$$x_i$$$ 的房子里。第 $$$i$$$ 位朋友可以到坐标 $$$x_i-1$$$、$$$x_i+1$$$ 的房子庆祝新年,或者住在 $$$x_i$$$。每个朋友只能移动一次。
对于所有朋友 $$$1 \le x_i \le n$$$ 成立,但是,他们可以来到坐标为 $$$0$$$ 和 $$$n+1$$$ 的房屋(如果他们的房屋分别位于 $$$1$$$ 或 $$$n$$$ 处)。
例如,假设初始位置为 $$$x = [1, 2, 4, 4]$$$。最后的可以是 $$$[1, 3, 3, 4]$$$, $$$[0, 2, 3, 3]$$$, $$$[2, 2, 5, 5]$$$, $$$[2, 1, 3, 5]$$$ 等等。占用房屋的数量是最终房屋中不同位置的数量。
所以所有的朋友都选择他们想要执行的动作。之后计算占用的房屋数量。最少和最多可容纳的房屋数量是多少?
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 好友数量。
第二行包含 $$$n$$$ 整数 $$$x_1, x_2, \dots, x_n$$$ ($$$1 \le x_i \le n$$$) — 朋友房子的坐标。
输出
打印两个整数——执行所有移动后可能占用的房屋的最小和最大数量。
示例
输入 #1
4 1 2 4 4
输出 #1
2 4
输入 #2
9 1 1 8 8 8 4 4 4 4
输出 #2
3 8
输入 #3
7 4 3 7 1 4 3 3
输出 #3
3 6
注意
在第一个例子中,朋友们可以去$$$[2, 2, 3, 3]$$$。所以朋友$$$1$$$去了$$$x_1+1$$$,朋友$$$2$$$住在他家$$$x_2$$$,朋友$$$3$$$去了$$$x_3-1$$$,朋友$$$4$$$去了$$$x_4-1$$$。 $$$[1, 1, 3, 3]$$$, $$$[2, 2, 3, 3]$$$ 或 $$$[2, 2, 4, 4]$$$ 也是获得 $$$2$$$ 已占用房屋的有效选项。
最多可入住的房屋数量朋友可以去$$$[1,2,3,4]$$$或者$$$[0,2,4,5]$$$。