← 返回题目列表

Codeforces · 1283/E

E. 新年派对

中文机器翻译题面 查看原题

哦,新年。是时候聚集所有朋友,回顾过去一年发生的感人事件了……

$$$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]$$$。