CF2249C Double-Rift Dial

A permutation $ ^{\text{∗}} $ $ p $ of length $ n $ is written clockwise on a circular dial. Choose a starting position $ s $ ( $ 1\le s\le n $ ) and read one full circle clockwise from $ p_s $ , wrapping around after $ p_n $ . The resulting sequence is $$$ q=[p_s,p_{s+1},\ldots,p_n,p_1,\ldots,p_{s-1}], $$$ which also has a length of $ n $ . For any non-empty prefix of this sequence $ [q_1, q_2, \ldots, q_k] $ ( $ k\ge 1 $ ), let $ S $ be the corresponding set of values, that is, $ S=\{q_1, q_2,\ldots, q_k\} $ . Split $ S $ into maximal segments of consecutive integers, and we call these segments the blocks of $ S $ . For example, $ S=\{1,2,5,7,8,9\} $ has $ 3 $ blocks: $ \{1,2\} $ , $ \{5\} $ , and $ \{7,8,9\} $ . A starting position $ s $ is called good if and only if, for every non-empty prefix of $ q $ , the corresponding set $ S $ has at most $ 2 $ blocks. Find the number of good starting positions. $ ^{\text{∗}} $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array).

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains one integer $ n $ ( $ 1\le n\le 2\cdot 10^5 $ ) — the length of $ p $ . The second line of each test case contains $ n $ integers $ p_1,p_2,\ldots,p_n $ ( $ 1\le p_i\le n $ , all $ p_i $ -s are distinct) — the elements of $ p $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10^5 $ .

For each test case, print one integer — the number of good starting positions.

In the first test case, there is only one starting position. Every non-empty prefix contains the single value $ 1 $ , so it has one block. Thus, this position is good. In the second test case, after reading the first $ 3 $ numbers from position $ 1 $ , the set is $ \{1,3,5\} $ and has $ 3 $ blocks. Thus, position $ 1 $ is not good. Each of the other $ 4 $ positions is good.