Вдоль прямой трассы расположено \(n\) посёлков. У каждого посёлка известна его координата на трассе — целое число \(p_i\). Связисты хотят покрыть все посёлки радиосигналом, установив на трассе несколько радиовышек.
Каждая вышка имеет радиус покрытия 1 километр: она покрывает всё, что находится на расстоянии не более 1 от её координаты. То есть вышка, установленная в точке \(x\), покрывает отрезок \([x - 1; \, x + 1]\). Посёлок считается покрытым, если его координата попадает в покрытие хотя бы одной вышки (граничная точка тоже считается покрытой).
Вышки можно ставить в любых точках прямой, в том числе с нецелыми координатами. Нужно установить минимальное количество вышек, чтобы все посёлки получили сигнал.
Формат входных данных
В первой строке — целое число \(n\) (\(1 \le n \le 10^5\)) — количество посёлков.
Во второй строке — \(n\) целых чисел \(p_i\) (\(-10^9 \le p_i \le 10^9\)), разделённых пробелами, — координаты посёлков. Координаты могут повторяться (несколько посёлков в одной точке).
Формат выходных данных
Одно целое число — минимальное количество радиовышек, необходимое для покрытия всех посёлков.
Примечание
В первом примере посёлки находятся в точках 1, 3, 5. Одна вышка, установленная в точке 2, покроет отрезок \([1; 3]\) и захватит посёлки в точках 1 и 3. Для посёлка в точке 5 нужна ещё одна вышка, например в точке 4 или в точке 5. Итого 2 вышки.
Во втором примере все посёлки близко друг к другу и покрываются одной вышкой.
| № | Входные данные | Выходные данные |
|
1
|
3
1 3 5
|
2
|
|
2
|
4
2 3 3 4
|
1
|