CF1151E Number of Components

克雷姆兰王国是一棵树（一个无环连通无向图），包含 $n$ 个顶点。每个顶点 $i$ 有一个权值 $a_i$。所有顶点通过边依次相连。具体来说，对于每个 $1 \leq i < n$，存在一条连接顶点 $i$ 和 $i+1$ 的边。 定义函数 $f(l, r)$，它接收两个整数 $l$ 和 $r$（$l \leq r$）： - 只保留权值在 $l$ 到 $r$ 范围内的顶点。 - 该函数的值为新图中的连通块数量。 你的任务是计算如下的和：$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r)$$

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示树的顶点数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$），表示每个顶点的权值。

输出一个整数，表示答案。

在第一个样例中，函数值如下： - $f(1, 1)=1$（只剩下编号为 $2$ 的顶点，形成一个连通块） - $f(1, 2)=1$（剩下编号为 $1$ 和 $2$ 的顶点，形成一个连通块） - $f(1, 3)=1$（所有顶点都保留，形成一个连通块） - $f(2, 2)=1$（只剩下编号为 $1$ 的顶点） - $f(2, 3)=2$（剩下编号为 $1$ 和 $3$ 的顶点，形成两个连通块） - $f(3, 3)=1$（只剩下编号为 $3$ 的顶点） 总和为 $7$。 在第二个样例中，函数值如下： - $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$（没有顶点剩下，连通块数量为 $0$） 总和为 $11$。 由 ChatGPT 4.1 翻译