Unlocking Unimodal Combination Lock

You are given a lock with ( n ) dials, forming a sequence ( {a} ). The lock will open if the sequence is unimodal, i.e., there exists an index ( i ) ((1 \le i \le n)) such that:

[ a_1 \le a_2 \le \cdots \le a_i \ge a_{i+1} \ge \cdots \ge a_n ]

Each dial displays a digit from 0 to 9. With a single twist, you can change a dial's digit to one of its two adjacent digits. Note that 0 and 9 are considered adjacent (i.e. shifting from 0 to 9 or 9 to 0 costs 1 move).

Find the minimum number of twists needed so that the lock shows a unimodal sequence.

Note: The distance between two digits ( d_1 ) and ( d_2 ) is defined as ( \min(|d_1-d2|, 10-|d_1-d_2|) ).

inputFormat

The first line contains an integer ( n ) ( (1 \le n \le 10^5) ), the number of dials on the lock. The second line contains ( n ) integers ( a_1, a_2, \ldots, a_n ) (each between 0 and 9) representing the current state of the lock.

outputFormat

Output a single integer: the minimum number of twists required to transform the current sequence into a unimodal sequence.

sample

1
5

0