#P17787. Outermost Maximums
Outermost Maximums
CF1693E Outermost Maximums
题目描述
有一个长度为 的序列 ,其中 ,其余元素均给定。
你可以进行下面两种操作任意次:
- 设 表示序列 最靠左的最大值的位置,则令 。
- 设 表示序列 最靠右的最大值的位置,则令 。
你需要求出使序列 的所有元素均变成 所需的最少的操作总次数。
输入格式
第一行输入一个整数 。
接下来一行输入 个整数 。
输出格式
输出一行一个整数表示使序列 的所有元素均变成 所需的最少的操作次数。
输入输出样例 #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
说明/提示
在第一个样例中,执行第一次操作得到 ,执行第二次操作得到 。
一种达成目标的方式如下所示(下划线标记最近一次修改的位置):
$\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$
在第三个样例中,每个元素已经为零,因此无需进行操作。