Người Gửi: Dương Lee
- Problem:
Có N quyển sách, đánh nhãn đôi một khác nhau từ 1 đến N xếp ngẫu nhiên trên một chồng. Bạn cần sắp xếp lại chồng sách theo thứ tự nhãn từ 1 đến N (tính từ đỉnh của chồng sách). Mỗi lượt di chuyển, bạn chỉ có thể lấy ra một quyển sách và đặt nó lên đỉnh của chồng sách.
Ví dụ: Nếu N=3, và thứ tự nhãn từ đỉnh ban đầu của chồng sách là {3,2,1}, bạn có thể lấy ra cuốn có nhãn là 2 và đặt lên đầu, chồng sách trở thành {2,3,1}. Tiếp theo, lấy cuốn có nhãn là 1, và đặt lên đầu, chồng sách trở thành {1,2,3}.
Nhiệm vụ của bạn là tìm xem cần tối thiểu bao nhiêu lượt di chuyển.
Input
Dòng 1: Số N (N ≤ 300 000)
N dòng tiếp theo, mỗi dòng chứa một số nguyên dương là nhãn của cuốn sách, dòng thứ i là nhãn của cuốn sách thứ i tính từ đỉnh.
Output
Số lần di chuyển tối thiểu
Example:
Input
3
3
2
1
Output:
2
Input
4
1
3
4
2
Output:
2
- Solution:
Input
4
1
3
4
2
Output:
2
Cách đặt tối ưu nhất:
- Xét i từ cuối lên đầu: và cuốn sách x;
+ Tại vị trí i đã đúng là sách x thì kiểm tra sách tiếp theo: x--;
+ Nếu không đúng thì đếm++ (có nghĩa là đã đưa sách lên đầu và không tính đến nó nữa) đi đếm vị trí tiếp theo.