# 描述

传送门：2018-2019 ACM-ICPC, Asia Jiaozuo Regional Contest - Problem H

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.