# 描述

You are given a sequence $\textbf{a}$ denoted by $(a_1, a_2, \cdots, a_n)$. A query with $1 \leq l \leq r \leq n$ is defined as
$Q_{max}(l, r) = \max\lbrace a_l, a_{l + 1}, \cdots, a_r\rbrace$.
An easy problem may ask you to calculate the sum of answers for all queries with integers $1 \leq l \leq r \leq n$, but we would like to show you a harder one.

Define a classifier as a container that stores unique elements. Each element in the classifier has two values, named the key value and the mapped value. The key value of each element is a consecutive subsequence of $\textbf{a}$ and the mapped value of that element is an integer indicating the maximum value in the subsequence. The classifier only stores elements with distinct key values, which means extra duplicated elements (with the same key value) would be removed from the classifier.

Denote $S(l, r)$ as $(a_l, a_{l + 1}, \cdots, a_r)$, a consecutive subsequence of $\textbf{a}$ meeting the condition that $l$ and $r$ are integers with $1 \leq l \leq r \leq n$. Now we intend to use a classifier $\textbf{CA}$ to store all the consecutive subsequences $S(l, r)$ of $\textbf{a}$ with their $Q_{max}(l, r)$. You are asked to determine the sum of mapped values in $\textbf{CA}$.

Actually, what we defined above is a map of the form map<vector<int>, int> in C++ or Map<ArrayList<Integer>, Integer> in Java, so if you are seasoned using these data structures, you may realize that what we intend to do is to insert all possible elements $(S(l, r), Q_{max}(l, r))$ with integers $1 \leq l \leq r \leq n$ into the classifier $\textbf{CA}$ and then ask you to calculate the sum of mapped values in it.

## Input

The input contains several test cases, and the first line contains a positive integer $T$ indicating the number of test cases which is up to $1000$.

For each test case, the first line contains an integer $n$ indicating the number length of the given sequence $\textbf{a}$, where $1 \leq n \leq 2 \times 10^5$.

The second line contains $n$ positive integers $a_1, a_2, \cdots, a_n$ describing the sequence $\textbf{a}$, where $1 \leq a_i \leq 10^6$.

We guarantee that there are at most $10$ test cases with $n > 1000$.

## Output

For each test case, output a line containing the sum of mapped values in $\textbf{CA}$.

## Note

In the first sample case, the sum of mapped values in $\textbf{CA}$ is equal to $1 + 2 + 3 + 2 + 3 + 3$.

In the second sample case, the sum of mapped values in $\textbf{CA}$ is equal to $2 + 3 + 3 + 3 + 3$.

# 思路

• 题意就是求所有本质不同的子段的最大值的和。
• 如果要求所有的子段，只需要用单调栈处理出每个数作为最大值的贡献即可。
• 考虑如何去除重复的子段：
• 用后缀数组把后缀排个序，利用 height 数组去重。
• 和求本质不同子串数量一样的思路，答案就是每个后缀的所有前缀的最大值的和减去相邻两个后缀的公共前缀的最大值的和
• 把后缀数组中的查询离线掉，逆序枚举左端点 $L$，用线段树维护到某个右端点 $R$ 的最大值。
• 这样就可以在线段树上区间求和得到某个后缀的前若干个前缀的最大值的和。
• 单调栈预处理右边第一个比它大的数的位置就可以在线段树上区间更新了。

0%