Description

Little M has a permutation $a$ of length $n$.

Little M can perform the following operation on an array $b$ of length $k$:

• Choose an index $i$ ($1\leq i\leq k$) and transform $b$ into $[b_i,b_{i+1},\cdots,b_{k},b_{1},b_{2},\cdots,b_{i-2},b_{i-1}]$. In other words, choose a suffix of $b$ and move it to the beginning.

The value $f(b)$ of the sequence $b$ is defined as the minimum number of operations to transform $b$ into a strictly increasing sequence. If it's impossible, $f(b)=0$.

You need to compute the value of $\sum\limits_{l=1}^{n}\sum\limits_{r=l}^{n}f([a_{l},a_{l+1},\cdots,a_{r-1},a_{r}])$, i.e., the sum of the values of all subarrays of $a$.

Input Format

The first line contains a positive integer $T$ — the number of test cases.

For each test case:

• The first line contains a positive integer $n$ — the length of the permutation.
• The second line contains a permutation $a$ of length $n$.

Output Format

Output $T$ lines, each containing an integer representing the answer for the corresponding test case.

12
1
1
2
1 2
2
2 1
3
1 2 3
3
1 3 2
3
2 1 3
3
2 3 1
3
3 1 2
3
3 2 1
6
1 2 5 6 3 4
9
9 8 7 6 5 4 3 2 1
12
1 2 3 4 5 6 7 8 9 10 11 12

0
0
1
0
1
1
2
2
2
4
8
0

Hint

Sample Explanation

For the third test case: Subarrays $[1,1],[2,2]$ are already strictly increasing sequences and there's no need to perform any operation. For subarray $[1,2]$, choosing $i=2$ transforms it into a strictly increasing sequence. Therefore, the answer is $0+0+1=1$.

For the sixth test case: For subarray $[1,2]$, choosing $i=2$ transforms it into a strictly increasing sequence. For subarray $[1,3]$, it can be proved that it's impossible to transform it into a strictly increasing sequence.

Constraints

Subtasks are used in this problem.

• Subtask 1 (15 pts): $n\leq10$, $\sum n\leq20$.
• Subtask 2 (35 pts): $n\leq10^3$, $\sum n\leq10^4$.
• Subtask 3 (30 pts): $n\leq10^5$, $\sum n\leq5\times10^5$.
• Subtask 4 (20 pts): No additional constraints.

For all test cases, it is guaranteed that $1\leq T\leq10^5$, $1\leq n\leq5\times10^6$ and $\sum n\leq10^7$.

Hint

The input can be a bit large, so you can add std::cin.tie(0)->sync_with_stdio(0) to the beginning of your program and use std::cin to read. It it guaranteed that you can read in all data within 600ms. Here is an example:

#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 1;
int T, n, ans, a[N];
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> T;
	while (T --) {
		cin >> n;
		for (int i = 1; i <= n; i ++)
			cin >> a[i];
		// compute the answer
		cout << ans << '\n';
	}
	return 0;
}