EZSORT - Sắp xếp là chuyện nhỏ!
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: middlest

Cho một dãy gồm n số nguyên dương a1, a2, a3, ..., an là một hoán vị của dãy các số từ 1 đến n. Ta có thể thực hiện thao tác biến đổi sau đây trên dãy: Chọn một phần tử ai bất kỳ (1 <= i <= n), sau đó xóa phần tử này khỏi dãy và chèn nó vào vị trí bên trái nhất của dãy. Hãy tìm số thao tác ít nhất để biến đổi dãy đã cho thành một dãy có giá trị tăng dần từ 1 đến n.

Dữ liệu vào

Dòng thứ nhất ghi số nguyên dương n

n dòng tiếp theo, dòng thứ i ghi số ai

Dữ liệu ra

Ghi ra một số duy nhất là thao tác ít nhất để biến đổi dãy đã cho thành một dãy có giá trị tăng dần từ 1 đến n.

Giới hạn

1 <= n <= 3x105

Ví dụ

  • input
    8
    5
    6
    7
    8
    1
    2
    4
    3
    output
    4
Back to Top