题目描述

给定长度为 $n$ 的序列 $a$，求所有 $a$ 的子区间的字典序最小的非空后缀的长度之和。

输入格式

本题有多组测试数据，第一行输入一个正整数 $T$，代表数据组数。

对于每组数据：

• 第一行输入一个正整数 $n$。
• 第二行输入 $n$ 个数，代表序列 $a$。

输出格式

对于每组数据，输出一行一个数，代表答案。

输入输出样例 #1

输入 #1

5
5
3 1 4 1 5
5
5 4 3 2 1
1
1
6
1 1 4 5 1 4
7
1 3 2 2 3 1 2

输出 #1

25
15
1
39
49

说明/提示

【样例解释】

对于样例的第一个测试数据，各子区间对应的字典序最小的非空后缀分别为：

• 区间 $[1,1]$ 的最小后缀为 $\{3\}$，长度为 $1$；
• 区间 $[2,2],[1,2],[4,4],[3,4],[2,4],[1,4]$ 的最小后缀为 $\{1\}$，长度均为 $1$；
• 区间 $[3,3]$ 的最小后缀为 $\{4\}$，长度为 $1$；
• 区间 $[5,5]$ 的最小后缀为 $\{5\}$，长度为 $1$；
• 区间 $[2,3],[1,3]$ 的最小后缀为 $\{1,4\}$，长度均为 $2$；
• 区间 $[4,5],[3,5]$ 的最小后缀为 $\{1,5\}$，长度均为 $2$；
• 区间 $[2,5],[1,5]$ 的最小后缀为 $\{1,4,1,5\}$，长度均为 $4$。

所有子区间的最小非空后缀长度之和为 $1\times 1 + 6\times 1 + 1\times 1 + 1\times 1 + 2\times 2 + 2\times 2 + 2\times 4 = 25$。

对于样例的第二个测试数据，序列 $a=\{5,4,3,2,1\}$ 共有 $15$ 个子区间。由于该序列单调递减，每个子区间字典序最小的非空后缀显然均为该区间最末尾的单个元素。因此，所有 $15$ 个子区间的最小非空后缀长度均为 $1$，总长度之和为 $15\times 1=15$。

【数据范围】

设 $\sum n$ 表示单个测试点内所有 $n$ 的总和。

对于所有数据，保证：

• $1\le T\le 10^5$；
• $1\le n\le 10^6$；
• $1\le \sum n\le 2\cdot 10^6$；
• $1\le a_i\le n$。

本题采用捆绑测试，各子任务特殊性质如下：

特殊性质：$\forall 1\le i<j\le n,a_i\neq a_j$。