Sắp xếp dãy số


Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 195M

Author:
Problem type

Cho 1 dãy số gồm n phần tử từ 1 đến n được sắp xếp ngẫu nhiên. Bạn hãy sắp xếp lại dãy số này theo thứ tự tăng dần với điều kiện ở mỗi bước sắp xếp bạn chỉ có thể chọn 1 vị trí bất kì và chuyển lên đầu dãy hoặc cuối dãy. Hãy tìm số bước tối thiểu để sắp xếp dãy.

Input:

  • Dòng đầu tiên là số nguyên n (0 < n < \(10^6\))
  • Dòng thứ 2 gồm n số từ 1 đến n

Output:

  • Dòng duy nhất gồm số bước sắp xếp tối thiểu

Example:

Input:

5
4 1 2 5 3

Output:

2

Comments

There are no comments at the moment.