题目描述

给定一个序列 $\mathbf{a}$，记作 $(a_1, a_2, \cdots, a_n)$。对于满足 $1 \leq l \leq r \leq n$ 的整数 $l, r$，定义查询

$$\displaystyle Q_{max}(l, r) = \max \lbrace a_l, a_{l + 1}, \cdots, a_r \rbrace .$$

一道简单的问题可能会要求你计算所有满足 $1 \leq l \leq r \leq n$ 的查询的答案之和，但我们想向你展示一道更难的题目。

定义一个分类器为一个存储不重复元素的容器。分类器中的每个元素拥有两个值，分别称为键值和映射值。每个元素的键值是 $\mathbf{a}$ 的一个连续子序列，而该元素的映射值则是一个整数，表示该子序列中的最大值。分类器只存储键值互不相同的元素，这意味着重复的额外元素（具有相同键值的元素）将被从分类器中移除。

记 $S(l, r)$ 为 $(a_l, a_{l + 1}, \cdots, a_r)$，即 $\mathbf{a}$ 的一个连续子序列，其中 $l$ 和 $r$ 为满足 $1 \leq l \leq r \leq n$ 的整数。现在我们打算用一个分类器 $\mathbf{CA}$ 来存储 $\mathbf{a}$ 的所有连续子序列 $S(l, r)$ 及其对应的 $Q_{max}(l, r)$。请你求出 $\mathbf{CA}$ 中所有映射值之和。

实际上，上文定义的正是一个 C++ 中形如 map<vector<int>, int> 或 Java 中形如 Map<ArrayList<Integer>, Integer> 的映射，因此如果你对这些数据结构运用自如，你可能会意识到我们要做的事情就是将满足 $1 \leq l \leq r \leq n$ 的所有可能的元素 $(S(l, r), Q_{max}(l, r))$ 插入分类器 $\mathbf{CA}$ 中，然后要求你计算其中映射值的总和。

输入格式

输入包含多组测试数据，第一行包含一个正整数 $T$，表示测试数据组数，最多可达 $1000$。

对于每组测试数据，第一行包含一个整数 $n$，表示给定序列 $\mathbf{a}$ 的长度，满足 $1 \leq n \leq 2 \times 10^5$。

第二行包含 $n$ 个正整数 $a_1, a_2, \cdots, a_n$，描述序列 $\mathbf{a}$，满足 $1 \leq a_i \leq 10^6$。

我们保证至多有 $10$ 组测试数据满足 $n > 1000$。

输出格式

对于每组测试数据，输出一行包含 $\mathbf{CA}$ 中所有映射值之和。

2
3
1 2 3
3
2 3 3

14
14

提示

在第一个样例中，$\mathbf{CA}$ 中映射值的总和等于 $1 + 2 + 3 + 2 + 3 + 3$。

在第二个样例中，$\mathbf{CA}$ 中映射值的总和等于 $2 + 3 + 3 + 3 + 3$。

翻译由 DeepSeek V4 Pro 完成