← 返回题目列表

Codeforces · 1693/E

E. 最外面的最大值

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

Yeri 有一个 $$$n + 2$$$ 非负整数数组:$$$a_0, a_1, ..., a_n, a_{n + 1}$$$。

我们知道 $$$a_0 = a_{n + 1} = 0$$$。

她想以最少的运算次数使$$$a$$$的所有元素都等于0。

在一次操作中,她可以执行以下操作之一:

- 选择最左边的最大元素并将其更改为其左侧元素的最大值。
- 选择最右边的最大元素并将其更改为其右侧元素的最大值。

帮助她找到使 $$$a$$$ 的所有元素都等于 0 所需的最少运算次数。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$)。

输出

打印单个整数 - 使 $$$a$$$ 的所有元素等于零所需的最少操作数。

示例

输入 #1

6
1 4 2 4 0 2

输出 #1

7

输入 #2

5
1 3 5 4 2

输出 #2

9

输入 #3

4
0 0 0 0

输出 #3

0

注意

在第一个示例中,执行第一个操作会得到 $$$\langle 1, \underline{1}, 2, 4, 0, 2 \rangle$$$,执行第二个操作会得到 $$$\langle 1, 4, 2, \underline{2}, 0, 2 \rangle$$$。

实现我们目标的一种方法如下所示。 (下划线显示最后的更改。) $$$\langle 1, 4, 2, 4, 0, 2 \rangle \to \langle 1, 4, 2, \underline{2}, 0, 2 \rangle \to \langle 1, \underline{1}, 2, 2, 0, 2 \rangle \to \langle 1, 1, 2, 2, 0, \underline{0} \rangle \to \langle 1, 1, 2, \underline{0}, 0, 0 \rangle \to \langle 1, 1, \underline{0}, 0, 0, 0 \rangle \to \langle \underline{0}, 1, 0, 0, 0, 0 \rangle \to \langle 0, \underline{0}, 0, 0, 0, 0 \角度 $$$

在第三个示例中,每个元素已经等于零,因此不需要任何操作。