GRETRAINS - SẮP XẾP TÀU
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
Một tuyến đường sắt dài vô tận có một đoàn tàu gồm n toa tàu được đánh số từ 1 đến n (số của tất cả các toa là khác biệt) và được định vị theo thứ tự tùy ý. Huy muốn sắp xếp chiếc xe lửa theo thứ tự tăng dần của các toa tàu.
Trong một lần di chuyển, anh ta có thể làm cho một trong những toa tàu biến mất khỏi vị trí của nó và dịch chuyển nó đến đầu tàu, hoặc đến cuối tàu theo mong muốn của anh ta. Số lượng hành động tối thiểu Huy cần thực hiện để sắp xếp tàu là bao nhiêu?
Dữ liệu nhập:
- Dòng đầu tiên của đầu vào chứa số nguyên n (1 ≤ n ≤ 100 000 ) - số lượng toa tàu trong xe lửa.
- Dòng thứ hai chứa n số nguyên pi ( 1 ≤ pi ≤ n , pi ≠ pj nếu i ≠ j ) - dãy số của các toa tàu trong tàu.
Kết quả:
- in một số nguyên duy nhất - số lượng hành động tối thiểu cần thiết để sắp xếp các toa xe lửa.
Ví dụ
input
5
4 1 2 5 3
output
2
input
4
4 1 3 2
output
2
```python
n = int(input())
p = list(map(int, input().split()))
pos = [0] * n
for i in range(n):
pos[p[i]-1] = i
count = 0
for i in range(n):
if pos[i] != i:
j = pos[i]
pos[i], pos[j] = pos[j], pos[i]
count += 1
print(count)
```
