О, Новый год. Лучшее время, чтобы собрать всех друзей вместе и окунуться в теплые воспоминания прошедшего года...
\(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]\) и так далее. Количество заполненных домов — это количество различных позиций среди конечных.
Теперь все друзья выбрали, куда пойти. После всех перемещений подсчитали количество заполненных домов. Какое минимальное и максимальное количество заполненных домов могло получиться?
Примечание
В первом примере друзья могут пойти в \([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]\), например.