{"problem":{"name":"『STA - R2』Locked","description":{"content":"这把锁从左到右有 $n$ 个数，组成了一个序列 $\\{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 的锁是拨动式的，即拨一下就能换成临近的一个数（$0$ 和 $9$ 可","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9408"},"statements":[{"statement_type":"Markdown","content":"这把锁从左到右有 $n$ 个数，组成了一个序列 $\\{a\\}$。\n\n由于 GOD_hj 的记性不好，所以只要将锁设置为输入任意单峰序列即可打开。具体为：\n$$ a_1 \\le \\cdots \\le a_i \\ge a_{i+1} \\ge \\cdots \\ge a_n\\quad (1 \\le i \\le n) $$\n\nGOD_hj 的锁是拨动式的，即拨一下就能换成临近的一个数（$0$ 和 $9$ 可以互换）。\n\n求最少拨几下可以开锁。\n\n## Input\n\n第一行一个整数，$n$。\n\n第二行 $n$ 个整数，为序列 $\\{a\\}$。\n\n## Output\n\n一个整数，为最少要拨动几下。\n\n[samples]\n\n## Background\n\nGOD_hj 有一把数字密码锁，但是他陷于 whk，没时间来开锁。\n\n## Note\n\n**【样例解释】**\n\n样例二：把第四个 $5$ 变为 $6$ 或把第三个 $6$ 变为 $5$。\n\n**【数据范围】**\n\n**本题采用捆绑测试。**\n\n$$\n\\newcommand{\\arraystretch}{1.5}\n\\begin{array}{c|c|c|c}\\hline\\hline\n\\textbf{Subtask} & \\bm n\\le &\\textbf{分值}&\\textbf{特殊性质} \\\\\\hline\n\\textsf{1} & 5 & 5 & \\textbf{无} \\\\\\hline\n\\textsf{2} & 10^3 & 25 & \\textbf{无} \\\\\\hline\n\\textsf{3}  & 5\\times 10^5 & 20 & \\textbf{无} \\\\\\hline\n\\textsf{4} & 5\\times 10^6 & 10 & a_i\\in\\{0,1\\} \\\\\\hline\n\\textsf{5} & 5\\times 10^6 & 40 & \\textbf{无} \\\\\\hline\\hline\n\\end{array}\n$$\n\n对于全部数据，$1\\le n\\le 5\\times 10^6$，$0\\le a_i<10$。\n\n**Upd on 2023/06/12**：新加 5 组 Hack 数据，放入 Subtask 6，不计分。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9408","tags":["O2优化"],"sample_group":[["3\n1 2 3","0"],["7\n1 2 6 5 6 7 2","1"]],"created_at":"2026-03-03 11:09:25"}}