有 $N$ 张卡片排成一行。为方便起见，将最左边的卡片记为第 1 张卡片，其后的卡片记为第 2 张卡片，$\dots$，最右边的卡片记为第 $N$ 张卡片。

这 $N$ 张卡片上各写有一个整数。设第 $i$ 张卡片上写的数为 $x_i$。

我们希望适当地修改这 $N$ 张卡片中部分卡片上的数字，使得从左到右卡片上的数字以固定的差值增加、减少，或者所有数字都相等。

修改卡片上的数字时只能改为整数值，且需要使修改的卡片数量最少。

例如，假设卡片的初始状态如下图所示。

在这种情况下，如果将第 3 张卡片上写的数修改为 3，就可以如下图所示使其每次增加 1，此时修改了数字的卡片数量为 1 张。

也可以如下图所示，让所有卡片上写的数都变为 2。此时，修改了数字的卡片数量为 2 张。

按从最左侧的卡片到最右侧的卡片的顺序给出每张卡片上写的数，求为了满足条件所需修改卡片数量的最小值。

数据范围

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

子任务

1. (3 分) $N \le 3$。
2. (10 分) 答案不超过 2。
3. (20 分) 保证在修改最少卡片以满足条件时，存在相邻卡片所写数字之差不超过 100 的情况。
4. (67 分) 无额外限制。

输入格式

第一行输入卡片的数量 $N$。

第二行按顺序以空格分隔输入各张卡片上所写的数 $x_i$。

输出格式

第一行输出答案。

样例

输入格式 1

4
1 2 2 4

输出格式 1

1

输入格式 2

5
6 3 3 1 -1

输出格式 2

2