C. Контрастность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для массива целых чисел $$$[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$$$?

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — размер массива $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \cdot, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — элементы массива.

Сумма $$$n$$$ по всем наборам входных данных не превышает $$$3 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — минимально возможное количество элементов в массиве $$$b$$$.

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