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

Перестановка$$$^{\text{∗}}$$$ $$$p$$$ длины $$$n$$$ записана по часовой стрелке на круговой шкале.

Выберите начальную позицию $$$s$$$ ($$$1\le s\le n$$$) и прочитайте один полный круг по часовой стрелке, начиная с $$$p_s$$$ и переходя после $$$p_n$$$ к началу. Получившаяся последовательность имеет вид

$$$$$$ q=[p_s,p_{s+1},\ldots,p_n,p_1,\ldots,p_{s-1}], $$$$$$

и тоже имеет длину $$$n$$$.

Для любого непустого префикса этой последовательности $$$[q_1, q_2, \ldots, q_k]$$$ ($$$k\ge 1$$$) пусть $$$S$$$ — соответствующее множество значений, то есть $$$S=\{q_1, q_2,\ldots, q_k\}$$$. Разобьём $$$S$$$ на максимальные отрезки последовательных целых чисел, и назовём эти отрезки блоками множества $$$S$$$.

Например, у множества $$$S=\{1,2,5,7,8,9\}$$$ есть $$$3$$$ блока: $$$\{1,2\}$$$, $$$\{5\}$$$ и $$$\{7,8,9\}$$$.

Начальная позиция $$$s$$$ называется хорошей тогда и только тогда, когда для каждого непустого префикса $$$q$$$ соответствующее множество $$$S$$$ имеет не более $$$2$$$ блоков.

Найдите количество хороших начальных позиций.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1,p_2,\ldots,p_n$$$ ($$$1\le p_i\le n$$$, все $$$p_i$$$ различны) — элементы $$$p$$$.

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

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

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

Пример
Входные данные
4
1
1
5
1 3 5 2 4
6
1 2 4 5 3 6
7
1 3 5 7 2 4 6
Выходные данные
1
4
3
0
Примечание

В первом наборе входных данных есть только одна начальная позиция. Каждый непустой префикс содержит единственное значение $$$1$$$, поэтому у него один блок. Следовательно, эта позиция хорошая.

Во втором наборе входных данных после чтения первых $$$3$$$ чисел, начиная с позиции $$$1$$$, множество равно $$$\{1,3,5\}$$$ и имеет $$$3$$$ блока. Следовательно, позиция $$$1$$$ не хорошая. Каждая из остальных $$$4$$$ позиций хорошая.