Number of Components
Contest: Codeforces Round 553 (Div. 2)
Difficulty rating: 2100
Tags: 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) $$$$$$

Input format:
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.

Output format:
Print one number — the answer to the problem.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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$$$)

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

Example input:
3
2 1 3

Example output:
7

Example input:
4
2 1 1 3

Example output:
11

Editorial:
First of all assign $$$0$$$ to $$$a_0$$$.
How to find the value of $$$f(l, r)$$$ in $$$\mathcal{O}(n)$$$?
For each $$$i$$$ from $$$0$$$ to $$$n$$$ set $$$b_i$$$ to $$$1$$$ if $$$l \leq a_i \leq r$$$, otherwise set it to $$$0$$$. Now we can see that the value of $$$f(l, r)$$$ is equal to the number of adjacent pairs $$$(0, 1)$$$ in array $$$b$$$.
So now we can find the answer in $$$\mathcal{O}(n)$$$ using technique contribution to the sum. For every adjacent pair of elements in array $$$a$$$ (including zero-indexed element) we must find it contribution to the overall answer. Considering the thoughts above about $$$f(l,r)$$$, we must find the number of pairs $$$(l, r)$$$ such that $$$a_i$$$ is on the range $$$[l, r]$$$ and $$$a_{i-1}$$$ is not on the range $$$[l, r]$$$. There are two cases:
What if $$$a_i$$$ is greater than $$$a_{i-1}$$$? Then $$$l$$$ must be on range from $$$a_{i-1}+1$$$ to $$$a_i$$$ and $$$r$$$ must be on range from $$$a_i$$$ to $$$n$$$. The contribution is $$$(a_i-a_{i-1}) \cdot (n-a_i+1)$$$.
What if $$$a_i$$$ is less than $$$a_{i-1}$$$? Then $$$l$$$ must be on range from $$$1$$$ to $$$a_i$$$ and $$$r$$$ must be on range from $$$a_i$$$ to $$$a_{i-1}-1$$$. The contribution is $$$a_i \cdot (a_{i-1} - a_i)$$$.
Sum up the contributions of all adjacent pairs to find the answer.
Complexity is $$$\mathcal{O}(n)$$$.