CF1787D Game on Axis

There are $ n $ points $ 1,2,\ldots,n $ , each point $ i $ has a number $ a_i $ on it. You're playing a game on them. Initially, you are at point $ 1 $ . When you are at point $ i $ , take following steps: - If $ 1\le i\le n $ , go to $ i+a_i $ , - Otherwise, the game ends. Before the game begins, you can choose two integers $ x $ and $ y $ satisfying $ 1\le x\le n $ , $ -n \le y \le n $ and replace $ a_x $ with $ y $ (set $ a_x := y $ ). Find the number of distinct pairs $ (x,y) $ such that the game that you start after making the change ends in a finite number of steps. Notice that you do not have to satisfy $ a_x\not=y $ .

Each test contains multiple test cases. The first line contains an integer $ t $ ( $ 1\le t\le 10^4) $ — the number of test cases. The first line of each test case contains one integer $ n $ ( $ 1\le n\le 2\cdot 10^5 $ ) — the number of points. The second line contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ -n \le a_i \le n $ ) — the numbers on the axis. It's guaranteed that the sum of $ n $ does not exceed $ 2\cdot 10^5 $ .

For each test case, print a line containing a single integer — the number of distinct pairs $ (x,y) $ with which the game ends.

In the first test case, the pairs $ (x,y) $ with which the game ends are $ (1,-1) $ and $ (1,1) $ , corresponding to the routes $ 1\rightarrow 0 $ and $ 1\rightarrow 2 $ . Note that $ (1,2) $ is invalid since when $ n=1 $ , $ y=2 $ violates $ -n\le y\le n $ . $ (1,0) $ is also invalid since you will go from $ 1 $ to $ 1 $ forever. In the second test case, the pairs are $ (1,-2),(1,-1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2) $ . In the fourth test case, the pairs are $ (1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,1),(2,2) $ .