Độ dài tối thiểu

Trong một buổi học, giảng viên đã giao cho nhóm FullHouse Dev một bài toán thú vị. Họ cần tìm cách sắp xếp một mảng số nguyên sao cho nó trở nên giống với một mảng khác. Để làm được điều này, họ có thể chọn bất kỳ phần tử nào trong mảng và di chuyển nó đến vị trí khác. Nhiệm vụ của nhóm là xác định số bước tối thiểu cần thiết để sắp xếp mảng theo thứ tự tăng dần hoặc giảm dần.

Bài toán

FullHouse Dev nhận được một mảng \(Arr\) chứa \(N\) số nguyên. Trong một bước, họ có thể chọn một phần tử tại vị trí \(p\) và đặt nó trước hoặc sau một số phần tử khác. Mục tiêu là tìm ra số bước tối thiểu cần thiết để 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 tiếp theo chứa \(N\) số nguyên - các phần tử của mảng \(Arr\).

OUTPUT FORMAT:

• In ra một số nguyên duy nhất, biểu thị số bước tối thiểu cần thiết để sắp xếp mảng.

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

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