H. 山形合影

Group Photo

时间限制：4 秒 · 内存限制：1024 MiB

原题：NWERC 2025 G · 查看官方英文原文（英文 PDF 也已作为本题附件提供）

题目描述

$n$ 名登山队员站成一排，身高互不相同。为方便起见，将他们的身高分别记为 $1$ 到 $n$。你希望最终的身高序列先严格递增，再严格递减，形成一个山形。递增部分或递减部分允许为空，因此完全递增或完全递减的序列也符合要求。

你可以选出一部分队员，让他们在这部分队员原先占据的位置之间任意重新排列；没有被选中的队员必须留在原位。

请问至少需要选出多少名队员，才能将整排队员排成符合要求的山形？

输入格式

第一行包含 $n$（$1 \leq n \leq 500000$）。

第二行包含 $n$ 个互不相同的整数 $a_{1}, \ldots , a_{n}$（$1 \leq a_{j} \leq n$），表示当前从左到右的身高序列。

输出格式

输出最少需要选出并重新安排位置的队员数量。

样例

6
1 6 4 3 2 5

2

5
4 3 2 1 5

4

4
1 2 4 3

0

10
1 2 7 4 5 6 3 8 9 10

2

原题版权归原作者及相应赛事评委会所有，采用 CC BY-SA 4.0 许可。中文译文为本练习赛整理，按相同许可发布。题号及中文标题作了调整，输入约束、样例和判题要求依照官方原题；图示及完整英文叙述请参阅英文原文附件。