Bartek là một nhà sản xuất nhạc techno nổi tiếng, và hiện anh đang hoàn thiện bản hit tiếp theo của mình. Anh đã tạo ra một bản nhạc gồm $n$ nhịp (beat), được đánh số liên tiếp từ $1$ đến $n$. Sau nhiều giờ làm việc trên phần mềm chỉnh sửa nhạc, khi chuẩn bị xuất tệp mp3, anh nhận ra rằng các nhịp hiện đang được sắp xếp theo thứ tự $a_1, a_2, \dots, a_n$. Bartek cần thu được thứ tự tăng dần của các nhịp, tức là $1, 2, \dots, n$.

Phần mềm cho phép hai loại thao tác:

• Di chuyển nhịp cuối cùng đến vị trí bất kỳ, ví dụ $(2, 4, 1, 5, \underline{3}) \to (2, \underline{3}, 4, 1, 5)$.
• Di chuyển một nhịp bất kỳ lên đầu, ví dụ $(2, 4, 1, \underline{5}, 3) \to (\underline{5}, 2, 4, 1, 3)$.

Số thao tác tối thiểu cần thiết để sắp xếp các nhịp theo thứ tự tăng dần là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 200\,000$), biểu thị số lượng nhịp.

Dòng thứ hai chứa $n$ số nguyên đôi một khác nhau $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n; a_i \ne a_j$), biểu thị thứ tự hiện tại của các nhịp trong phần mềm.

Kết quả

In ra một số nguyên duy nhất – số thao tác tối thiểu cần thực hiện.

Ví dụ

Dữ liệu vào 1

6
3 2 5 4 1 6

Kết quả 1

4

Dữ liệu vào 2

9
3 1 2 5 6 4 9 7 8

Kết quả 2

6

Ghi chú

Ta bắt đầu với dãy nhịp $(3, 2, 5, 4, 1, 6)$. Dưới đây là một cách để đạt được thứ tự mong muốn sau bốn thao tác:

• Di chuyển nhịp cuối cùng sang trái hai vị trí: $(3, 2, 5, \underline{6}, 4, 1)$.
• Di chuyển nhịp $2$ lên đầu: $(\underline{2}, 3, 5, 6, 4, 1)$.
• Di chuyển nhịp $1$ lên đầu: $(\underline{1}, 2, 3, 5, 6, 4)$.
• Di chuyển nhịp cuối cùng sang trái hai vị trí: $(1, 2, 3, \underline{4}, 5, 6)$.

Có thể thu được thứ tự tăng dần theo những cách khác bằng bốn thao tác, nhưng không thể thực hiện trong ba thao tác, vì vậy kết quả là $4$.