Outermost Maximums

题意翻译

### 题目描述 有一个长度为 $n+2$ 的序列 $a$，其中 $a_0=a_{n+1}=0$，其余元素均给定。 你可以进行下面两种操作任意次： 1. 设 $x$ 表示序列 $a$ 最靠左的最大值的位置，则令 $a_x\leftarrow \max_{i=0}^{x-1}a_i$。 2. 设 $y$ 表示序列 $a$ 最靠右的最大值的位置，则令 $a_y\leftarrow \max_{i=y+1}^{n+1}a_i$。 你需要求出使序列 $a$ 的所有元素均变成 $0$ 所需的最少的操作总次数。 ### 输入格式 第一行输入一个整数 $n(1\leq n\leq2\times10^5)$。 接下来一行输入 $n$ 个整数 $a_1,a_2,\cdots,a_{n}(0\leq a_i\leq n)$。 ### 输出格式 输出一行一个整数表示使序列 $a$ 的所有元素均变成 $0$ 所需的最少的操作次数。 ### 样例解释 对于样例一，下面展示了一种进行 $7$ 次操作的操作方案： - 下面的序列 $a$ 省略 $a_0$ 和 $a_{n+1}$。 - 第一步进行操作二，此时最靠右的最大值的位置是 $4$，操作后 $a=\{1,4,2,2,0,2\}$。 - 第二步进行操作一，此时最靠左的最大值的位置是 $2$，操作后 $a=\{1,1,2,2,0,2\}$。 - 接下来继续进行五次操作二，即可达成要求。

题目描述

Yeri has an array of $ n + 2 $ non-negative integers : $ a_0, a_1, ..., a_n, a_{n + 1} $ . We know that $ a_0 = a_{n + 1} = 0 $ . She wants to make all the elements of $ a $ equal to zero in the minimum number of operations. In one operation she can do one of the following: - Choose the leftmost maximum element and change it to the maximum of the elements on its left. - Choose the rightmost maximum element and change it to the maximum of the elements on its right. Help her find the minimum number of operations needed to make all elements of $ a $ equal to zero.

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ). The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le n $ ).

输出格式

Print a single integer — the minimum number of operations needed to make all elements of $ a $ equal to zero.

输入输出样例

输入样例 #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

说明

In the first sample, you get $ \langle 1, \underline{1}, 2, 4, 0, 2 \rangle $ by performing the first operation and $ \langle 1, 4, 2, \underline{2}, 0, 2 \rangle $ by performing the second operation. One way to achieve our goal is shown below. (The underlines show the last change.) $ \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 \rangle $ In the third sample each element is already equal to zero so no operations are needed.

题意翻译

### 题目描述 有一个长度为 $n+2$ 的序列 $a$，其中 $a_0=a_{n+1}=0$，其余元素均给定。 你可以进行下面两种操作任意次： 1. 设 $x$ 表示序列 $a$ 最靠左的最大值的位置，则令 $a_x\leftarrow \max_{i=0}^{x-1}a_i$。 2. 设 $y$ 表示序列 $a$ 最靠右的最大值的位置，则令 $a_y\leftarrow \max_{i=y+1}^{n+1}a_i$。 你需要求出使序列 $a$ 的所有元素均变成 $0$ 所需的最少的操作总次数。 ### 输入格式 第一行输入一个整数 $n(1\leq n\leq2\times10^5)$。 接下来一行输入 $n$ 个整数 $a_1,a_2,\cdots,a_{n}(0\leq a_i\leq n)$。 ### 输出格式 输出一行一个整数表示使序列 $a$ 的所有元素均变成 $0$ 所需的最少的操作次数。 ### 样例解释 对于样例一，下面展示了一种进行 $7$ 次操作的操作方案： - 下面的序列 $a$ 省略 $a_0$ 和 $a_{n+1}$。 - 第一步进行操作二，此时最靠右的最大值的位置是 $4$，操作后 $a=\{1,4,2,2,0,2\}$。 - 第二步进行操作一，此时最靠左的最大值的位置是 $2$，操作后 $a=\{1,1,2,2,0,2\}$。 - 接下来继续进行五次操作二，即可达成要求。