#P17787. Outermost Maximums

Outermost Maximums

CF1693E Outermost Maximums

题目描述

有一个长度为 n+2n+2 的序列 aa,其中 a0=an+1=0a_0=a_{n+1}=0,其余元素均给定。

你可以进行下面两种操作任意次:

  1. 设 xx 表示序列 aa 最靠左的最大值的位置,则令 ax←max⁡i=0x−1aia_x\leftarrow \max_{i=0}^{x-1}a_i。
  2. 设 yy 表示序列 aa 最靠右的最大值的位置,则令 ay←max⁡i=y+1n+1aia_y\leftarrow \max_{i=y+1}^{n+1}a_i。

你需要求出使序列 aa 的所有元素均变成 00 所需的最少的操作总次数。

输入格式

第一行输入一个整数 n(1≤n≤2×105)n(1\leq n\leq2\times10^5)。

接下来一行输入 nn 个整数 a1,a2,⋯ ,an(0≤ai≤n)a_1,a_2,\cdots,a_{n}(0\leq a_i\leq n)。

输出格式

输出一行一个整数表示使序列 aa 的所有元素均变成 00 所需的最少的操作次数。

输入输出样例 #1

输入 #1

6
1 4 2 4 0 2

输出 #1

7

输入输出样例 #2

输入 #2

5
1 3 5 4 2

输出 #2

9

输入输出样例 #3

输入 #3

4
0 0 0 0

输出 #3

0

说明/提示

在第一个样例中,执行第一次操作得到 ⟨1,1‾,2,4,0,2⟩\langle 1, \underline{1}, 2, 4, 0, 2 \rangle,执行第二次操作得到 ⟨1,4,2,2‾,0,2⟩\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$

在第三个样例中,每个元素已经为零,因此无需进行操作。