Sắp xếp học viên

Bối cảnh

Hiếu đang cố gắng sắp xếp \(N\) học viên của mình \((1≤N≤100)\), được đánh số tiện lợi từ \(1\) đến \(N\). Hiện tại, các học viên đang đứng thành một hàng theo thứ tự \(p_1, p_2, p_3,\dots, p_N,\) và Hiếu đang đứng trước học viên \(p_1\). Anh ấy muốn sắp xếp lại các học viên sao cho chúng đứng theo thứ tự \(1, 2, 3,\dots, N,\) với học viên 1 đứng cạnh Hiếu.

Yêu cầu

Các học viên hôm nay hơi buồn ngủ, vì vậy vào bất kỳ thời điểm nào, chỉ có học viên đang đối diện với Hiếu mới chú ý đến lời hướng dẫn của anh. Anh có thể chỉ đạo học viên này di chuyển \(k\) bước xuống hàng, với mọi \(k\) trong khoảng từ \(1\) đến \(N-1\). Các học viên mà người đó đi qua sẽ di chuyển về phía trước, tạo chỗ để học viên ấy chen vào hàng sau họ.

Ví dụ, giả sử \(N=4\) và các học viên bắt đầu ở thứ tự sau:

Hiếu: \(4, 3, 2, 1\) Học viên duy nhất đang chú ý đến Hiếu là học viên số \(4\). Nếu anh ta chỉ đạo cô ấy di chuyển \(2\) bước xuống hàng, thứ tự sau đó sẽ trông như thế này:

Hiếu: \(3, 2, 4, 1\) Bây giờ học viên duy nhất đang chú ý đến Hiếu là học viên số \(3\), vì vậy trong bước thứ hai anh ta có thể đưa ra hướng dẫn cho học viên số \(3\), và cứ thế cho đến khi các học viên được sắp xếp.

Hiếu rất muốn hoàn thành việc sắp xếp, để anh có thể trở về với ny của mình. Hãy giúp anh ấy tìm ra số bước thời gian tối thiểu cần thiết để sắp xếp các học viên.

Input

Dòng đầu tiên của đầu vào chứa \(N\).

Dòng thứ hai chứa \(N\) số nguyên cách nhau bằng dấu cách, \(p_1, p_2, p_3,\dots, p_N,\) chỉ thứ tự bắt đầu của các học viên.

Output

Một số nguyên duy nhất: số bước caanf ddeer sắp xếp theo thứ tự, nếu Hiếu hành động một cách tối ưu.

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

4
1 2 4 3

Output

3

Giải thích ví dụ

• Ví dụ: N = 4, thứ tự: 1 2 4 3
  • Giải thích: Hiếu chỉ đạo học viên 4 di chuyển xuống 2 bước, sau đó học viên 3 và 4 được điều chỉnh để hoàn thành sắp xếp. Tổng cộng cần 3 bước để có thứ tự 1, 2, 3, 4.

Thông tin học tập

• Buổi: B10
• Concepts: 1D arrays, suffix traversal
• Giới hạn kiến thức: B01-B10
• Time limit: 1 second
• Memory limit: 20 MB
• Point: 40