luogu#P9408. 『STA - R2』Locked

『STA - R2』Locked

题目背景

GOD_hj 有一把数字密码锁,但是他陷于 whk,没时间来开锁。

题目描述

这把锁从左到右有 nn 个数,组成了一个序列 {a}\{a\}

由于 GOD_hj 的记性不好,所以只要将锁设置为输入任意单峰序列即可打开。具体为:

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

GOD_hj 的锁是拨动式的,即拨一下就能换成临近的一个数(0099 可以互换)。

求最少拨几下可以开锁。

输入格式

第一行一个整数,nn

第二行 nn 个整数,为序列 {a}\{a\}

输出格式

一个整数,为最少要拨动几下。

3
1 2 3
0
7
1 2 6 5 6 7 2
1

提示

【样例解释】

样例二:把第四个 55 变为 66 或把第三个 66 变为 55

【数据范围】

本题采用捆绑测试。

$$\newcommand{\arraystretch}{1.5} \begin{array}{c|c|c|c}\hline\hline \textbf{Subtask} & \bm n\le &\textbf{分值}&\textbf{特殊性质} \\\hline \textsf{1} & 5 & 5 & \textbf{无} \\\hline \textsf{2} & 10^3 & 25 & \textbf{无} \\\hline \textsf{3} & 5\times 10^5 & 20 & \textbf{无} \\\hline \textsf{4} & 5\times 10^6 & 10 & a_i\in\{0,1\} \\\hline \textsf{5} & 5\times 10^6 & 40 & \textbf{无} \\\hline\hline \end{array} $$

对于全部数据,1n5×1061\le n\le 5\times 10^60ai<100\le a_i<10

Upd on 2023/06/12:新加 5 组 Hack 数据,放入 Subtask 6,不计分。