EZSORT - Sắp xếp là chuyện nhỏ!

EZSORT - Sắp xếp là chuyện nhỏ!

Cho một dãy gồm n số nguyên dương a₁, a₂, a₃, ..., a_n 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ử a_i 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ố a_i

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 <= 3x10⁵

Ví dụ

·         input

8
5
6
7
8
1
2
4
3

output

4

//CONST   fi='EZSORT.INP';  fo='EZSORT.OUT';

VAR n,i,d:longint;    a:array[1..500000] of longint;

BEGIN

          readln(n);

          for i:=1 to n do readln(a[i]);

          d:=n;

          for i:=n downto 1 do

                   If a[i]=d then dec(d);

          write(d);

END.

kiểu dữ liệu tệp

//CONST   fi='EZSORT.INP';  fo='EZSORT.OUT';

VAR n,i,d:longint;    a:array[1..500000] of longint;

f1,f2:text;

BEGIN

assign(f1,'EZSORT.INP');

assign(f2,'EZSORT.out');

reset(f1);rewrite(f2);

          readln(f1,n);

          for i:=1 to n do readln(f1,a[i]);

          d:=n;

          for i:=n downto 1 do

                   If a[i]=d then dec(d);

          write(f2,d);

close(f1);close(f2);

END.