В порядке подготовки к предстоящему турниру Фермер Джон учит \(N\) своих коров
(последовательно пронумерованных \(1\dots N\), где \(1 \leq N \leq 100\)) в передаче
мяча. Все коровы стоят вдоль длинной прямой линии на одной стороне амбара
корова \(i\) стоит на \(x_i\) единиц от амбара (\(1 \leq x_i \leq 1000\)). Все коровы
находятся в различных позициях.
В начале тренировки ФД бросает несколько мячей различных коровам. Когда корова
\(i\) получает мяч, от ФД или от другой коровы, она передаёт мяч ближайшей к ней
корове. Если таких коров несколько, то она передаёт мяч самой левой из них.
ФД хочет обеспечить, чтобы каждая корова хоть один раз получила мяч. Помогите ФД
определить минимальное количество мячей, которое он должен бросить изначально,
(правильному подмножеству коров), чтобы каждая корова хоть один раз получила мяч.
ФОРМАТ ВВОДА (файл hoofball.in):
Первая строка ввода содержит \(N\). Вторая строка содержит \(N\) целых чисел,
разделённых одиночными пробелами, где \(i\)-ое число - есть \(x_i\).
ФОРМАТ ВЫВОДА (файл hoofball.out):
Выведите минимальное количество мячей, которые изначально ФД должен отпасовать
коровам так, чтобы каждая корова получила мять хоть однажды.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
7 1 3 11 4
|
2
|