配点 : 500 点
問題文
Noboru 您购买了拨号键。这个拨号键 编号至 1 减去 N 由 N 表盘组成,每个表盘都有一个 0 以上 9 设置以下数字。目前,所有拨打的号码均为 它用 0 初始化。
该拨号键的密码是 N 序列 使用 A 什么时候可以工作 1 \leq i \leq N 的 对于 i 拨打关于 号码 i 是 只有匹配 A_i 时,拨号键才会打开。
Noboru 您的目标如下。操作该值应乘以 0 多次按住拨号键打开。 选择
操作 : 1 \leq l \leq r \leq N 的整数 选择 l, r 并执行以下操作之一:
拨号 l,l+1,\ldots,r 中的每个数字 添加 1 。然而,操作之前的数字是 9 如果 而不是添加 1 替换为 0 。
拨号 l,l+1,\ldots,r 中的每个数字 减去 1 。然而,操作之前的数字是 而不是减去 0 如果 而不是添加 1 它 9 。
他希望通过尽可能少的操作来实现他的目标。求最少的操作次数。
制約
- 1 \leq N \leq 10^5
- 0 \leq A_i \leq 9 (1 \leq i \leq N)
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N A_1 A_2 \ldots A_N
出力
输出最小操作次数。
入力例 1
3 2 1 9
出力例 1
3
例如,可以考虑以下操作步骤。
-
l=1, r=1 并将每个拨号号码设置为 添加 1 。表盘上的数字是 1,0,0 变为。
-
l=1, r=2 并将每个拨号号码设置为 添加 1 。表盘上的数字是 2,1,0 变为。
-
l=3, r=3 并且,从各个拨号数字中 1 减去。拨号数字 2,1,9 变为。
2 无法通过不超过次数的操作将拨号键置于开启状态,因此, 3 。
入力例 2
6 3 1 4 1 5 9
出力例 2
11
入力例 3
1 0
出力例 3
0
因为拨号键已经打开,所以Noboru君一次都不需要操作。
由于拨号的数字本来就与 <var>A</var> 匹配,所以不需要操作。原案: Noboru2020