克雷姆兰王国是一棵树(无环的连通无向图),由 $$$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$$$) - 顶点的值。
输出
打印一个数字——问题的答案。
示例
输入 #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
注意
在第一个示例中,函数值如下:
- $$$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$$$)
在第二个示例中,函数值如下:
- $$$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$$$)