← 返回题目列表

AtCoder · tkppc6_1_k

K. 拨号键

中文机器翻译题面 查看原题

配点 : 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

例如,可以考虑以下操作步骤。

  1. l=1, r=1 并将每个拨号号码设置为 添加 1 。表盘上的数字是 1,0,0 变为。

  2. l=1, r=2 并将每个拨号号码设置为 添加 1 。表盘上的数字是 2,1,0 变为。

  3. 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