Số bước tối thiểu

Trong một buổi thử nghiệm ứng dụng di động mới, FullHouse Dev đang phát triển một tính năng sắp xếp thông minh cho điện thoại. Để tối ưu hóa thuật toán, họ cần giải quyết một bài toán thú vị về việc di chuyển các phần tử trong mảng với số bước ít nhất có thể.

Bài toán

Cho một mảng \(Arr\) gồm \(N\) số nguyên. Trong mỗi bước, bạn có thể chọn một phần tử ở vị trí \(p\) và đặt nó trước hoặc sau một số phần tử khác. Nhiệm vụ của bạn là xác định số bước tối thiểu cần thực hiện để sắp xếp mảng theo thứ tự tăng dần hoặc giảm dần.

INPUT FORMAT:

• Dòng đầu tiên chứa một số nguyên \(N\) - kích thước của mảng
• Dòng thứ hai chứa \(N\) số nguyên, trong đó số thứ \(i\) biểu thị \(Arr[i]\)

OUTPUT FORMAT:

• In ra một số nguyên duy nhất biểu thị số bước tối thiểu cần thực hiện để sắp xếp mảng theo thứ tự tăng dần hoặc giảm dần.

Ràng buộc:

• \(1 \leq N \leq 10^5\)
• \(1 \leq Arr[i] \leq 10^9\)

Ví dụ

INPUT

3
1 3 2

OUTPUT

1

Giải thích

Cho mảng \(Arr = \{1,3,2\}\).

• Để sắp xếp theo thứ tự tăng dần thành {1,2,3}, cần 1 bước.
• Để sắp xếp theo thứ tự giảm dần thành {3,2,1}, cũng cần 1 bước. Do đó, số bước tối thiểu là 1.