Number of Components

题意翻译

有一条$n(1 \leq n \leq 10^5)$个节点的链，编号相邻节点有边，每个点一个权值$a_i(1 \leq a_i \leq n)$，$f(l,r)$定义为权值在$[l,r]$的点中的连通块数量求$\sum_{l=1}^{n}\sum_{r=l}^{n}f(l,r)$

题目描述

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.

输入输出样例

输入样例 #1

3
2 1 3

输出样例 #1

7

输入样例 #2

4
2 1 1 3

输出样例 #2

11

输入样例 #3

10
1 5 2 5 5 3 10 6 5 1

输出样例 #3

104

说明

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