P9408 『STA - R2』Locked

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

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.

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

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

**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