小 M 有一个长度为 n 的排列 a。
对于一个长度为 k 的序列 b，小 M 可以执行以下操作：
- 选择一个满足 1≤i≤k 的位置 i，将序列变为 [bi,bi+1,⋯,bk,b1,b2,⋯,bi-2,bi-1]。也就是说，将 b 的一个后缀移到开头。
定义序列 b 的价值 f(b) 为「将 b 变成严格上升序列的最小操作数」。若无法通过操作变成严格上升序列，则 f(b)=0。
你需要求出 
，
即 a 中所有子串的价值之和。
小 M 有一个长度为 n 的排列 a。
对于一个长度为 k 的序列 b，小 M 可以执行以下操作：
定义序列 b 的价值 f(b) 为「将 b 变成严格上升序列的最小操作数」。若无法通过操作变成严格上升序列，则 f(b)=0。
你需要求出 ，
即 a 中所有子串的价值之和。
第一行一个正整数 T 表示测试数据组数。
对于每组数据：
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
对于第三组样例：区间 [1,1],[2,2] 已经是严格上升序列，不需要操作。而对于区间 [1,2]，选择 i=2 即可将其变为严格上升序列。故答案为 0+0+1=1。
对于第六组样例：区间 [1,2] 可以通过一次 i=2 的操作变为严格上升序列，而对于区间 [1,3]，可以证明无论如何操作都无法将其排序。
本题开启子任务捆绑测试。
对于所有数据，保证 1≤T≤10^5，1≤n≤5×10^6，∑n≤10^7。