CF1693E.Outermost Maximums

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.

耶莉有一个长度为 $n + 2$ 的非负整数数组：$a_0, a_1, ..., a_n, a_{n + 1}$。

已知 $a_0 = a_{n + 1} = 0$。

她希望以最少的操作次数，使数组 $a$ 的所有元素都变为零。

每次操作中，她可以执行以下两种操作之一：

• 选择最左侧的最大元素，并将其值更改为其左侧所有元素的最大值；
• 选择最右侧的最大元素，并将其值更改为其右侧所有元素的最大值。

请帮她求出将数组 $a$ 的所有元素变为零所需的最少操作次数。

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$).

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

第二行包含 $n$ 个整数 $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.

输出一个整数——使数组 $a$ 的所有元素变为零所需的最少操作次数。

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.

在第一个样例中，执行第一次操作得到 $\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 \rangle $

在第三个样例中，每个元素已经为零，因此无需任何操作。