logo AlgoBeat OnlineJudge
登录 注册

#215301. [NWERC 2025] Group Photo

内存限制:2048 MiB 时间限制:4000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

No-Weather-too-Extreme Recreational Climbing 协会的成员们今天完成了他们的第 次成功登顶!为了纪念这一时刻,你将拍摄一张所有成员站成一排的照片。

年前的第 次登顶照片变成了一场中等规模的灾难之后,你决定这次要正确处理,确保在拍照人们以美观的方式排列。

由于这个团体全是关于登山,你希望照片中登山者的身高形成山的形状。更准确地说,登山者应被排列成身高先递增后递减(递增或递减部分允许为空)。所有登山者的身高两两不同,因此为简单起见,我们将说最矮的登山者身高为 ,第二矮的登山者身高为 ,依此类推。

登山者们已经以某种任意的方式站成一排,这不一定美观。你将选择登山者的一个子集,并在他们之间重新排列位置,所有其他登山者保持原位。为了将混乱降至最低,你希望移动的登山者数量尽可能少。最小的登山者子集的大小是多少,使得可以重新排序他们,从而使身高序列先递增后递减?

输入格式

输入包含:

  • 一行,一个整数 (),表示登山者的数量。
  • 一行, 个不同的整数 (对每个 ),其中 是当前排列中第 个登山者的身高。

输出格式

输出需要移动的登山者的最小数量。

样例

样例输入 1

6
1 6 4 3 2 5

样例输出 1

2

样例输入 2

5
4 3 2 1 5

样例输出 2

4

样例输入 3

4
1 2 4 3

样例输出 3

0

样例输入 4

10
1 2 7 4 5 6 3 8 9 10

样例输出 4

2

数据范围与提示

样例 #1 解释。 交换第一个和最后一个登山者是最优方式,使得身高序列先递增后递减。