Một chuỗi đá quý kết nối thành vòng tròn. Bạn hãy tìm cách bỏ đi một số viên đá để vòng đá còn lại, theo chiều kim đồng hồ, có giá trị tăng dần (tính từ một vị trí nào đó).

Dữ liệu:

• Dòng đầu tiên chứa số nguyên dương n ≤ 10^4;
• Dòng tiếp theo chứa n số nguyên dương a1, a2,…, an là giá trị lần lượt của các viên đá (theo chiều kim đồng hồ). (ai ≤ 10^9)

Kết quả: ghi ra số viên đá ít nhất phải loại bỏ để thỏa mãn yêu cầu.

Ví dụ

Input

6
2 6 1 7 3 4

Output

2

Giải thích ví dụ:

Loại bỏ 2 viên có giá trị 2 và 7. Vòng còn lại là 1, 3, 4, 6.

Cũng có cách khác là bỏ 2 viên giá trị 1 và 2. Khi đó, vòng còn lại là 3, 4, 6, 7.

Nguồn