← 返回题目列表

Codeforces · 1151/E

E. 组件数量

中文机器翻译题面 查看原题

克雷姆兰王国是一棵树(无环的连通无向图),由 $$$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$$$)