Для массива целых чисел \([a_1, a_2, \dots, a_n]\) значение \(|a_1-a_2|+|a_2-a_3|+\cdots+|a_{n-1}-a_n|\) назовем контрастностью массива. Обратите внимание, что контрастность массива размера \(1\) равен \(0\).
Дан массив целых чисел \(a\). Ваша задача — построить массив \(b\) таким образом, чтобы выполнялись следующие условия:
- \(b\) не пустой, то есть содержит хотя бы один элемент;
- \(b\) является подпоследовательностью \(a\), то есть \(b\) может быть получен удалением некоторых элементов из \(a\) (возможно, ни одного);
- контрастность \(b\) равна контрастности \(a\).
Каково минимально возможное количество элементов в массиве \(b\)?
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимально возможное количество элементов в массиве \(b\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5
1 3 3 3 7
2
4 2
4
1 1 1 1
7
5 4 2 1 0 0 4
|
2
2
1
3
|