405667: GYM102028 H Can You Solve the Harder Problem?

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\{a_l, a_{l + 1}, \cdots, a_r\}.$$$$$$ 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.

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$$$.

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

2
3
1 2 3
3
2 3 3

14
14

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$$$.