Есть $$$n$$$ точек $$$1,2,\ldots,n$$$, у каждой точки $$$i$$$ написано число $$$a_i$$$. Вы играете в игру на этих точках. Изначально вы находитесь в точке $$$1$$$. Когда вы находитесь в точке $$$i$$$, выполните следующий шаг:
Перед началом игры вы можете выбрать два целых числа $$$x$$$ и $$$y$$$, удовлетворяющих $$$1\le x\le n$$$, $$$-n \le y \le n$$$, и заменить число $$$a_x$$$ на $$$y$$$ (сделать $$$a_x := y$$$). Найдите количество различных пар $$$(x,y)$$$, при которых игра, которую вы начнете после замены, закончится за конечное число шагов.
Обратите внимание, что вам не нужно удовлетворять условию $$$a_x\not=y$$$.
Каждый тест содержит несколько наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1\le t\le 10^4)$$$ — количество наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — количество точек.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$-n \le a_i \le n$$$) — числа на оси.
Гарантируется, что сумма $$$n$$$ не превосходит $$$2\cdot 10^5$$$.
Для каждого набора входных данных выведите строку, содержащую одно целое число — количество различных пар $$$(x,y)$$$, игра с которыми конечна.
9102-1 021 -121 13-1 -2 -131 -2 -14-1 4 -2 151 1 1 1 -451 1 1 1 1
2 8 6 7 20 17 34 30 40
В первом наборе входных данных парами $$$(x,y)$$$, с которыми игра конечна, являются $$$(1,-1)$$$ и $$$(1,1)$$$, соответствующие маршрутам $$$1\rightarrow 0$$$ и $$$1\rightarrow 2$$$. Обратите внимание, что пара $$$(1,2)$$$ не подходит, так как при $$$n=1$$$ равенство $$$y=2$$$ нарушает $$$-n\le y\le n$$$. $$$(1,0)$$$ также не подходит, так как вы всегда переходите от $$$1$$$ к $$$1$$$, и игра не заканчивается.
Во втором наборе входных данных подходящие пары равны $$$(1,-2),(1,-1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2)$$$.
В четвертом наборе входных данных подходящие пары $$$(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,1),(2,2)$$$.
Название |
---|