Tại một xưởng chế biến gỗ, người ta có \(N\) tấm gỗ được xếp thành một hàng theo thứ tự từ \(1\) đến \(N\). Sau khi gia công, mỗi tấm gỗ có một chiều cao xác định, không nhất thiết bằng nhau. Để đảm bảo tính thẩm mỹ, người thợ muốn giữ lại một số tấm gỗ sao cho khi nhìn từ đầu hàng đến cuối hàng, chiều cao các tấm gỗ còn lại thỏa mãn một trong hai dạng sau:

• Tăng nghiêm ngặt: mỗi tấm đứng sau có chiều cao lớn hơn tấm đứng trước;
• Giảm nghiêm ngặt: mỗi tấm đứng sau có chiều cao nhỏ hơn tấm đứng trước.

Người thợ được phép loại bỏ tùy ý một số tấm gỗ khỏi hàng.

Yêu cầu: Hãy xác định số lượng tấm gỗ ít nhất cần loại bỏ để dãy còn lại thỏa mãn một trong hai điều kiện trên.

Input

• Dòng 1: chứa số nguyên dương \(N\) (\(1 \le N \le 10^5\));
• Dòng 2: chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)), trong đó \(a_i\) là chiều cao của tấm gỗ thứ \(i\).

Output

• Ghi ra một số nguyên duy nhất là số tấm gỗ cần loại bỏ ít nhất.

Example

5
1 4 2 3 9

1

7
8 1 7 3 5 2 1

2

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N \le 25\);
• Subtask \(2\) (\(30\%\) số điểm): \(N \le 2000\);
• Subtask \(3\) (\(30\%\) số điểm): \(N \le 10^5\).