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 \角度 $$$
在第三个示例中,每个元素已经等于零,因此不需要任何操作。