B. Холмы и долины
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана последовательность $$$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}}$$$.

Определим страшность последовательности как сумму числа холмов и числа долин этой последовательности. Разрешается заменить ровно одно число в последовательности на любое другое, либо оставить последовательность без изменений. Какое минимальное значение страшности при этом можно достигнуть?

Входные данные

В первой строке входных данных содержится единственное целое число $$$t$$$ ($$$1 \le t \le 10000$$$) — количество наборов входных данных. Затем следуют описания самих наборов.

Первая строка каждого набора содержит единственное целое число $$$n$$$ ($$$1 \le n \le 3\cdot10^5$$$).

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$), разделенных пробелами.

Гарантируется, что сумма $$$n$$$ во всех наборах входных данных не превышает $$$3\cdot10^5$$$.

Выходные данные

Для каждого набора входных данных требуется вывести единственное целое число — минимальное значение страшности, которое может быть достигнуто при заданных входных данных.

Пример
Входные данные
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
Примечание

В первом наборе входных данных изменение значения $$$a_2$$$ на $$$2$$$ приведет к тому, что холмов и долин не будет.

Во втором наборе входных данных наилучшим решением будет оставить массив без изменений.

В третьем наборе входных данных изменение значения $$$a_3$$$ на $$$6$$$ приведет к тому, что будет только одна долина (с индексом $$$5$$$).

В четвертом наборе входных данных изменение значения $$$a_3$$$ на $$$6$$$ приведет к тому, что холмов и долин не будет.