Для массива целых чисел \([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\)?
Первая строка содержит одно целое число \(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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач