9118: Non-Puzzle: Error Permutation

You are given a permutation $P$ of length $n$. Find the number of its subsegments [l…r][l\dots r][l…r](l≤rl \le rl≤r) that satisfies the following condition:

• ∀1≤i≤r−l+1\forall 1\le i \le r-l+1∀1≤i≤r−l+1 , the $i$-th element of this subsegment (that is, Pl+i−1P_{l+i-1}Pl+i−1) is not the $i$-th smallest element in this subsegment.

There are multiple test cases.
The first line contains one integer $T$ (1≤T≤10001\le T \le 10001≤T≤1000), representing the number of test cases.
For each test case, the first line contains a single integer $n$ ($1\le n\le 5000$), representing the length of the permutation.
The following line contains $n$ integers p1,p2…pnp_{1},p_{2} \dots p_{n}p1,p2…pn, representing the permutation.
It is guaranteed that the sum of $n$ does not exceed $5000$.

For each test case, output a line containing a single integer representing the answer.