Дана последовательность \(n\) целых чисел \(a_1\), \(a_2\), ..., \(a_n\). Назовем индекс \(j\) (\(2 \le j \le {{n-1}}\)) холмом, если \(a_j > a_{{j+1}}\) и \(a_j > a_{{j-1}}\); и назовем его долиной, если \(a_j < a_{{j+1}}\) и \(a_j < a_{{j-1}}\).
Определим страшность последовательности как сумму числа холмов и числа долин этой последовательности. Разрешается заменить ровно одно число в последовательности на любое другое, либо оставить последовательность без изменений. Какое минимальное значение страшности при этом можно достигнуть?
Выходные данные
Для каждого набора входных данных требуется вывести единственное целое число — минимальное значение страшности, которое может быть достигнуто при заданных входных данных.
Примечание
В первом наборе входных данных изменение значения \(a_2\) на \(2\) приведет к тому, что холмов и долин не будет.
Во втором наборе входных данных наилучшим решением будет оставить массив без изменений.
В третьем наборе входных данных изменение значения \(a_3\) на \(6\) приведет к тому, что будет только одна долина (с индексом \(5\)).
В четвертом наборе входных данных изменение значения \(a_3\) на \(6\) приведет к тому, что холмов и долин не будет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
1 5 3
5
2 2 2 2 2
6
1 6 2 5 2 10
5
1 6 2 5 1
|
0
0
1
0
|