贡献名单

题目背景

namespace INPUT_SPACE{const int S=(1<<20)+5;char B[S],*H,*T;inline int gc() { if(H==T) T=(H=B)+fread(B,1,S,stdin);return (H==T)?EOF:*H++; }inline int inn() { int x,ch,f=1;while((ch=gc())<'0'||ch>'9')if(ch=='-')f=-1;x=ch^'0';while((ch=gc())>='0'&&ch<='9') x=x*10+(ch^'0');return x*f; }}using INPUT_SPACE::inn;

题目描述

我们在题目背景处提供了一个快速输入工具，它可以在大约 100 毫秒内完成本题的所有输入。您可以复制它并使用函数inn() 读入一个无符号 32 位整数。该工具的来源为此处。

小 M 有一个排列 $\{a_n\}$。

对于一个序列 $\{b_k\}$，小 M 可以执行以下操作：

• 选择一个位置 $1\leq i\leq k$，将序列变为 $[b_i,b_{i+1},\cdots,b_{k},b_{1},b_{2},\cdots,b_{i-2},b_{i-1}]$。（也就是说，将 $\{b_k\}$ 的一个后缀移到开头。）

定义序列 $\{b_k\}$ 的价值 $f(b)$ 为「将 $b$ 变成严格上升子序列的最小操作数」，若无法变成变成严格上升子序列，则 $f(b)=0$。

你需要求出 $\sum\limits_{l=1}^{n}\sum\limits_{r=l}^{n}f([a_{l},a_{l+1},\cdots,a_{r-1},a_{r}])$，即 $a$ 中所有子串的 $f$ 值之和。

输入格式

第一行一个正整数 $T$ 表示测试数据组数。

对于每组数据，第一行一个正整数 $n$，表示排列长度。

第二行一个长度为 $n$ 的排列 $\{a_n\}$。

输出格式

输出共 $T$ 行，第 $i$ 行一个整数表示第 $i$ 组测试数据的答案。

样例 #1

样例输入 #1

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

样例输出 #1

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

说明/提示

【样例解释 #1】

对于第三组样例，区间 $[1,1],[2,2]$ 两个区间内的数已经排序，不需要操作。而对于区间 $[1,2]$，选择 $i=2$，操作后序列 $b=[2,1]$ 变为序列 $b=[1,2]$，成功排序。故答案为 $0+0+1=1$。

对于第六组样例，区间 $[1,2]$ 可以通过一次 $i=2$ 的操作排序，区间 $[2,3]$ 已经排序。而对于区间 $[1,3]$，可以证明无论如何操作都无法将其排序。

【数据范围与约定】

• Subtask 1（20 pts）：$n\leq10$，$\sum n\leq20$。
• Subtask 2（30 pts）：$n\leq10^3$，$\sum n\leq10^4$。
• Subtask 3（30 pts）：$n\leq10^5$，$\sum n\leq5\times10^5$。
• Subtask 4（20 pts）：无特殊限制。

对于所有数据，$1\leq T\leq10^5$，$1\leq n\leq5\times10^6$，$\sum n\leq10^7$。