Có $N$ thẻ bài được xếp thành một hàng. Để thuận tiện, ta gọi thẻ bài ngoài cùng bên trái là thẻ 1, thẻ tiếp theo là thẻ 2, $\dots$, và thẻ ngoài cùng bên phải là thẻ $N$.

Trên mỗi thẻ trong số $N$ thẻ bài có ghi một số nguyên. Gọi số ghi trên thẻ thứ $i$ là $x_i$.

Bạn muốn thay đổi các số ghi trên một số thẻ trong số $N$ thẻ bài một cách thích hợp sao cho từ trái sang phải, các số ghi trên thẻ bài tăng đều, giảm đều, hoặc tất cả các số đều bằng nhau.

Khi thay đổi số ghi trên thẻ bài, bạn chỉ có thể đổi thành các giá trị nguyên, và số lần thay đổi phải là ít nhất có thể.

Ví dụ, giả sử các thẻ bài được cho như hình bên dưới.

Trong trường hợp này, nếu đổi số ghi trên thẻ thứ 3 thành 3, ta có thể làm cho dãy số tăng đều mỗi lần 1 đơn vị như hình bên dưới, và số lượng thẻ cần đổi số là 1.

Bạn cũng có thể làm cho các số ghi trên tất cả các thẻ đều bằng 2 như sau. Khi đó, số lượng thẻ cần đổi số là 2.

Cho các số ghi trên từng thẻ bài theo thứ tự từ thẻ ngoài cùng bên trái đến thẻ ngoài cùng bên phải, hãy tìm số lượng thẻ bài tối thiểu cần phải thay đổi để thỏa mãn điều kiện.

Giới hạn

• $2 \le N \le 500$
• Với mọi $1 \le i \le N$, $-1\ 000\ 000 \le x_i \le 1\ 000\ 000$

Subtask

1. (3 điểm) $N \le 3$.
2. (10 điểm) Đáp án không vượt quá 2.
3. (20 điểm) Đảm bảo luôn tồn tại một cách thay đổi ít thẻ bài nhất để thỏa mãn điều kiện sao cho độ chênh lệch giữa hai số ghi trên hai thẻ kề nhau không vượt quá 100.
4. (67 điểm) Không có ràng buộc gì thêm.

Dữ liệu vào

Dòng đầu tiên chứa số lượng thẻ bài $N$.

Dòng thứ hai chứa các số $x_i$ ghi trên từng thẻ bài theo thứ tự, cách nhau bởi dấu cách.

Dữ liệu ra

In ra đáp án trên dòng đầu tiên.

Ví dụ

Dữ liệu vào 1

4
1 2 2 4

Dữ liệu ra 1

1

Dữ liệu vào 2

5
6 3 3 1 -1

Dữ liệu ra 2

2