Хуфбол#10406
Готуючись до майбутнього турніру з хуфболу, фермер Джон тренує своїх корів (зручно пронумерованих 1, \ldots, n) у передачах м'яча. Корови стоять у дуже довгому ряду з одного боку від сараю, причому корова стоїть на відстані x_i одиниць від сараю. Усі корови стоять у різних позиціях.
На початку тренування фермер Джон передасть кілька м'ячів різним коровам. Щоразу, коли корова отримує м'яч, чи то від фермера Джона, чи то від іншої корови, вона передає його найближчій до себе корові. Якщо декілька корів знаходяться на однаковій відстані від неї, вона передає м'яч найлівішій з них. Щоб кожна корова отримала хоча б трохи практики в передачах, фермер Джон хоче переконатися, що кожна корова хоча б раз потримає м'яч. Допоможіть йому знайти мінімальну кількість м'ячів, які йому потрібно роздати на початку, щоб цього досягти, вважаючи, що він обирає відповідний початковий набір корів, яким їх передати.
Перший рядок містить ціле число n~(1 \le n \le 100). Другий рядок містить цілих чисел, де -те число є x_i~(1 \le x_i \le 1000).
Виведіть мінімальну кількість м'ячів, які фермер Джон повинен спочатку передати коровам, щоб кожна корова хоча б раз потримала м'яч.
У прикладі фермер Джон повинен передати один м'яч корові на позиції x = 1 та ще один м'яч корові на позиції x = 11. Корова на позиції x = 1 передає свій м'яч корові на позиції x = 3, після чого цей м'яч постійно курсує туди-сюди між коровами на позиціях x = 3 та x = 4. Корова на позиції x = 11 передає свій м'яч корові на позиції x = 7, яка передає його корові на позиції x = 4, після чого цей м'яч також починає курсувати між коровами на позиціях x = 3 та x = 4. Таким чином, кожна корова хоча б раз отримує м'яч — чи то від фермера Джона, чи то від іншої корови.
Легко побачити, що не існує жодної окремої корови, якій фермер Джон міг би передати один-єдиний м'яч так, щоб його врешті-решт отримали всі корови.
Приклад 1