Background

GOD_hj has a digital combination lock, but he is stuck with whk and has no time to unlock it.

Problem Description

This lock has $n$ digits from left to right, forming a sequence $\{a\}$.

Because GOD_hj has a poor memory, the lock can be opened as long as it is set to any unimodal sequence. More specifically:

$$a_1 \le \cdots \le a_i \ge a_{i+1} \ge \cdots \ge a_n\quad (1 \le i \le n)$$

GOD_hj's lock is a dial-type lock: with one dial move, a digit can be changed to an adjacent digit ($0$ and $9$ can be switched to each other).

Find the minimum number of dial moves needed to open the lock.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers, the sequence $\{a\}$.

Output Format

Output one integer, the minimum number of dial moves required.

3
1 2 3

0

7
1 2 6 5 6 7 2

1

Hint

Sample Explanation

Sample 2: Change the fourth $5$ to $6$, or change the third $6$ to $5$.

Constraints

This problem uses bundled testdata.

$$\newcommand{\arraystretch}{1.5} \begin{array}{c|c|c|c}\hline\hline \textbf{Subtask} & \bm n\le &\textbf{Score}&\textbf{Special Property} \\\hline \textsf{1} & 5 & 5 & \textbf{None} \\\hline \textsf{2} & 10^3 & 25 & \textbf{None} \\\hline \textsf{3} & 5\times 10^5 & 20 & \textbf{None} \\\hline \textsf{4} & 5\times 10^6 & 10 & a_i\in\{0,1\} \\\hline \textsf{5} & 5\times 10^6 & 40 & \textbf{None} \\\hline\hline \end{array}$$

For all testdata, $1\le n\le 5\times 10^6$, $0\le a_i<10$.

Upd on 2023/06/12: 5 new hack testdata sets were added and placed into Subtask 6, not scored.

Translated by ChatGPT 5