P12697 [KOI 2022 Round 2] 更换卡片

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

桌面上放置了 $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$，表示从左到右每张卡片上写的数，数之间用空格分隔。

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

**约束条件** - $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 分）无额外限制条件