E. Number of Components
combinatorics; data structures; dp; math
The Kingdom of Kremland is a tree (a connected undirected graph without cycles) consisting of \(n\) vertices. Each vertex \(i\) has its own value \(a_i\). All vertices are connected in series by edges. Formally, for every \(1 \leq i < n\) there is an edge between the vertices of \(i\) and \(i+1\).Denote the function \(f(l, r)\), which takes two integers \(l\) and \(r\) (\(l \leq r\)): We leave in the tree only vertices whose values ​​range from \(l\) to \(r\). The value of the function will be the number of connected components in the new graph. Your task is to calculate the following sum: $$$\(\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) \)$$$
The first line contains a single integer \(n\) (\(1 \leq n \leq 10^5\)) — the number of vertices in the tree.The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq n\)) — the values of the vertices.
Print one number — the answer to the problem.
In the first example, the function values ​​will be as follows: \(f(1, 1)=1\) (there is only a vertex with the number \(2\), which forms one component) \(f(1, 2)=1\) (there are vertices \(1\) and \(2\) that form one component) \(f(1, 3)=1\) (all vertices remain, one component is obtained) \(f(2, 2)=1\) (only vertex number \(1\)) \(f(2, 3)=2\) (there are vertices \(1\) and \(3\) that form two components) \(f(3, 3)=1\) (only vertex \(3\)) Totally out \(7\).In the second example, the function values ​​will be as follows: \(f(1, 1)=1\) \(f(1, 2)=1\) \(f(1, 3)=1\) \(f(1, 4)=1\) \(f(2, 2)=1\) \(f(2, 3)=2\) \(f(2, 4)=2\) \(f(3, 3)=1\) \(f(3, 4)=1\) \(f(4, 4)=0\) (there is no vertex left, so the number of components is \(0\)) Totally out \(11\).