시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB83584267.742%

문제

Мало кто знает, что Цинна с детства увлекается изобразительным искусством. Раньше он часами проводил время, стоя перед холстом с палитрой в руках. Вот и сейчас, увидя давно забытую кисть, он с радостью вспоминает правило, которое позволяет получить огромное количество удивительных цветов: из цветов с номерами $a$ и $b$ можно получить цвет с номером $\lfloor \frac{a+b}{2} \rfloor$. Цинну стало интересно, сколько различных цветов можно получить из имеющихся. Помогите ему разобраться с этим!

입력

В первой строке входного файла находится число $n$ ($1 \le n \le 10^5$) --- количество цветов, имеющихся у Цинны.

Во второй строке входного файла находятся $n$ чисел $a_i$ ($1 \le a_i \le 10^9$) --- номера цветов.

Цвета могут повторяться.

Можно считать, что у Цинны имеется неограниченное количество заданных цветов.

Обратите внимание, что операцию можно применять и над получившимися в результате другой операции цветами.

출력

Выведите максимальное количество различных цветов, которые может получить Цинна.

예제 입력 1

6
5 7 10 12 8 4

예제 출력 1

9