問題文

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)
• 入力は全て整数

入力例 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 君は一度も操作を行う必要がありません。

原案: Noboru2020