$N$ 枚のカードが置かれている。便宜上、一番左にあるカードを 1 番のカード、その次にあるカードを 2 番のカード $\dots$ 一番右にあるカードを $N$ 番のカードとしよう。

$N$ 枚のカードにはそれぞれ整数が 1 つずつ書かれている。$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点) 追加の制約はない。

入力

1 行目にカードの枚数 $N$ が与えられる。

2 行目には各カードに書かれた数 $x_i$ が空白区切りで順番に与えられる。

出力

1 行目に答えを出力せよ。

入出力例

入出力例

入力 1

4
1 2 2 4

出力 1

1

入出力例

入力 2

5
6 3 3 1 -1

出力 2

2