D. Разделение пути
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана последовательность из $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$.

Вы хотите разбить $$$a$$$ на несколько подпоследовательностей$$$^{\text{∗}}$$$ $$$b_1,b_2,\ldots,b_k$$$, удовлетворяющих следующим условиям:

  • Каждый элемент в $$$a$$$ принадлежит ровно одной из $$$b_i$$$.
  • Для каждой последовательности $$$b_i$$$, пусть её элементы будут $$$b_{i,1},b_{i,2},\ldots,b_{i,p_i}$$$. Для каждого $$$1\le j \lt p_i$$$ должно выполняться условие $$$|b_{i,j}-b_{i,j+1}|=1$$$.

Пожалуйста, вычислите минимальное количество подпоследовательностей, на которые вы можете разбить $$$a$$$.

$$$^{\text{∗}}$$$Последовательность $$$b_i$$$ является подпоследовательностью $$$a$$$, если $$$b_i$$$ может быть получена из $$$a$$$ удалением нескольких (возможно, ни одного или всех) элементов на произвольных позициях.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n\le10^6$$$) — длина последовательности $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le2n$$$) — последовательность $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

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

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

Пример
Входные данные
7
1
1
1
2
8
11 13 10 11 11 11 13 10
6
8 8 6 7 7 7
3
5 1 3
10
11 14 14 13 12 14 12 10 14 12
1
2
Выходные данные
1
1
5
3
3
7
1
Примечание

В первом наборе входных данных мы можем разбить $$$a$$$ на подпоследовательности $$$[1]$$$. Очевидно, что мы не можем разбить $$$a$$$ на меньшее количество подпоследовательностей; таким образом, ответ равен $$$1$$$.

В третьем наборе входных данных мы можем разбить $$$a$$$ на подпоследовательности $$$[11,10,11,10],[13],[11],[11],[13]$$$. Обратите внимание, что $$$[11,10,11,11,11,10]$$$ не является допустимой последовательностью, так как $$$|11-11|=0\neq1$$$.