给定一个序列 $\mathbf{a}$，记作 $(a_1, a_2, \dots, a_n)$。对于 $1 \le l \le r \le n$，定义查询为 $$Q_{max}(l, r) = \max\{a_l, a_{l+1}, \dots, a_r\}$$

一个简单的问题可能会要求你计算所有满足 $1 \le l \le r \le n$ 的查询结果之和，但我们想展示一个更难的问题。

定义一个分类器（classifier）为一个存储唯一元素的容器。分类器中的每个元素都有两个值，分别称为键值（key value）和映射值（mapped value）。每个元素的键值是 $\mathbf{a}$ 的一个连续子序列，而该元素的映射值是一个整数，表示该子序列中的最大值。分类器仅存储具有不同键值的元素，这意味着多余的重复元素（具有相同键值的元素）将从分类器中移除。

记 $S(l, r)$ 为 $(a_l, a_{l+1}, \dots, a_r)$，即 $\mathbf{a}$ 的一个满足 $1 \le l \le r \le n$ 的连续子序列。现在我们打算使用一个分类器 $\mathbf{CA}$ 来存储 $\mathbf{a}$ 的所有连续子序列 $S(l, r)$ 及其对应的 $Q_{max}(l, r)$。你需要确定 $\mathbf{CA}$ 中所有映射值的总和。

实际上，我们上述定义的内容等同于 C++ 中的 map<vector<int>, int> 或 Java 中的 Map<ArrayList<Integer>, Integer>。因此，如果你熟悉这些数据结构，你可能会意识到我们想要做的是将所有可能的元素 $(S(l, r), Q_{max}(l, r))$（其中 $1 \le l \le r \le n$）插入到分类器 $\mathbf{CA}$ 中，然后计算其中映射值的总和。

输入格式

输入包含多个测试用例。第一行包含一个正整数 $T$，表示测试用例的数量，最多为 $1000$。

对于每个测试用例，第一行包含一个整数 $n$，表示给定序列 $\mathbf{a}$ 的长度，其中 $1 \le n \le 2 \times 10^5$。

第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，描述序列 $\mathbf{a}$，其中 $1 \le a_i \le 10^6$。

我们保证 $n > 1000$ 的测试用例不超过 $10$ 个。

输出格式

对于每个测试用例，输出一行，包含 $\mathbf{CA}$ 中映射值的总和。

样例

输入 1

2
3
1 2 3
3
2 3 3

输出 1

14
14

说明

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

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