题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

桌面上放置了 $N$ 张卡片。为方便描述，我们将最左边的卡片称为第 1 张卡片，接下来的称为第 2 张卡片，以此类推，最右边的卡片为第 $N$ 张卡片。

每张卡片上都写有一个整数。记第 $i$ 张卡片上写的数为 $x_i$。

你可以选择更改这 $N$ 张卡片中部分卡片上写的数字，使得从左到右卡片上的数字呈现以下三种形式之一：

• 单调递增（每张卡片上的数比左边那张卡片上的数大相同的量）；
• 单调递减（每张卡片上的数比左边那张卡片上的数小相同的量）；
• 所有卡片上的数都相同。

你只能将卡片上的数改为整数，并且需要使改动的卡片数量尽可能少。

例如，考虑下面的情况：卡片上的数依次为 1、2、2、4。

你可以将第 3 张卡片上的数字改为 3，这样卡片上的数就依次为 1、2、3、4，满足每张卡片上的数字比左边一张大 1。此时只更改了 1 张卡片。

或者，你可以将第 1 张和第 4 张卡片上的数字都改为 2，使所有卡片上的数字都变为 2，此时共更改了 2 张卡片。

给定从最左边到最右边所有卡片上原本写的数，请计算为了满足上述任意一种形式，最少需要更改多少张卡片。

输入格式

第一行包含一个整数 $N$，表示卡片的数量。

第二行包含 $N$ 个整数 $x_1, x_2, \ldots, x_N$，表示从左到右每张卡片上写的数，数之间用空格分隔。

输出格式

输出一个整数，表示为了满足条件需要更改的卡片数量的最小值。

4
1 2 2 4

1

5
6 3 3 1 -1

2

提示

约束条件

• $2 \leq N \leq 500$
• 对所有 $1 \leq i \leq N$，有 $-1\,000\,000 \leq x_i \leq 1\,000\,000$

子任务

1. （3 分）$N \leq 3$
2. （10 分）最少只需更改不超过 2 张卡片
3. （20 分）保证存在一种最优解使得相邻卡片上数的差值不超过 100
4. （67 分）无额外限制条件