E. Новогодние посиделки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

О, Новый год. Лучшее время, чтобы собрать всех друзей вместе и окунуться в теплые воспоминания прошедшего года...

$$$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$$$) — координаты домов друзей.

Выходные данные

Выведите два целых числа — минимальное и максимальное количество заполненных домов, которые могли получиться после всех перемещений.

Примеры
Входные данные
4
1 2 4 4
Выходные данные
2 4
Входные данные
9
1 1 8 8 8 4 4 4 4
Выходные данные
3 8
Входные данные
7
4 3 7 1 4 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]$$$, например.