Контрольні точки
Джо — досвідчений програміст. Керівництво дорожньої поліції хоче контролювати рух на автомагістралі та найняло його для вирішення наступної задачі. На автомагістралі є певні фіксовані контрольні точки. Вони хочуть розмістити спеціальні пристрої, які збиратимуть інформацію з усіх цих точок. Оскільки такі пристрої дуже дорогі, кожен з них може покривати лише один метр (включаючи ліву кінцеву точку та виключаючи праву). Завдання полягає в тому, щоб розмістити мінімальну кількість пристроїв для покриття всіх контрольних точок. Джо має знайти ефективне рішення.
Вхідні дані
Вхідні дані зчитуються з текстового файлу. Кожен набір даних у файлі описує певну конфігурацію контрольних точок. Набір починається з числа n (n ≤ 100000) — кількість контрольних точок, за яким слідують дійсні числа в порядку зростання, що представляють координати цих точок (автомагістраль вважається дійсною лінією). Координати виражені в метрах. Пробіли можуть вільно зустрічатися у вхідних даних. Вхідні дані завершуються кінцем файлу.
Вихідні дані
Для кожного набору даних програма повинна вивести мінімальну кількість пристроїв, необхідних для покриття всіх контрольних точок, на стандартний вихід.
Приклад вхідних/вихідних даних наведено в таблиці нижче. Є два набори даних. У першому випадку є 2 точки: 3.56 та 4. Потрібен лише один пристрій.