Копитобол
Готуючись до майбутнього турніру з копиту, фермер Джон тренує своїх n корів (пронумерованих від 1 до n), передаючи м'яч. Усі корови стоять уздовж довгої лінії з одного боку корівника, і корова i розташована на відстані x[i] одиниць від корівника. Кожна корова має своє унікальне місце.
На початку вправи фермер Джон передає кілька м'ячів різним коровам. Коли корова i отримує м'яч від фермера Джона або від іншої корови, вона передає м'яч найближчій до неї корові (якщо кілька корів знаходяться на однаковій відстані, вона передає м'яч лівій корові). Щоб усі корови мали можливість потренуватися в передачі, фермер Джон хоче переконатися, що кожна корова хоча б раз тримає м'яч. Допоможіть йому визначити мінімальну кількість м'ячів, які потрібно роздати на початку, щоб це стало можливим, за умови, що він передає м'ячі відповідній початковій групі корів.
Вхідні дані
Перший рядок містить число n (1 ≤ n ≤ 100). Другий рядок містить n цілих чисел, де i-те число - це x[i] (1 ≤ x[i] ≤ 1000).
Вихідні дані
Виведіть мінімальну кількість м'ячів, які фермер Джон повинен спочатку передати коровам, щоб кожна корова змогла тримати м'яч хоча б один раз.
Приклад
У наведеному прикладі фермер Джон повинен передати м'яч корові на позиції x = 1 і корові на позиції x = 11. Корова на позиції x = 1 передасть свій м'яч корові на позиції x = 3, після чого цей м'яч буде передаватися між коровами на позиціях x = 3 і x = 4. Корова на позиції x = 11 передасть свій м'яч корові на позиції x = 7, яка передасть м'яч корові на позиції x = 4, після чого цей м'яч також буде переміщатися між коровами на позиціях x = 3 і x = 4. Таким чином, усі корови отримають передачу принаймні один раз (від фермера Джона або від іншої корови).
Очевидно, що немає жодної корови, якій фермер Джон міг би спочатку передати м'яч так, щоб кожна корова зрештою отримала м'яч.