Problem
Khi chơi một trò chơi mới (một số trò chơi kết hợp giữa bowling và bida), N quả bóng được sử dụng, được đánh số từ 1 đến N. Khi bắt đầu trò chơi, những quả bóng này phải được xếp thành hàng theo thứ tự số. Trong trò chơi, thứ tự của chúng có thể thay đổi.
Để sắp xếp các quả bóng trước khi bắt đầu trò chơi tiếp theo, thiết bị sau đây được sử dụng. Thiết bị này bao gồm một cái đầu, khi di chuyển trên các quả bóng, có thể "hút" và "nhổ ra" bóng bay. Để hiểu rõ hơn về thiết bị này, hãy tưởng tượng một chiếc máy hút bụi có thể hút các quả bóng vào, di chuyển đến đúng nơi và ở đó, thổi theo hướng ngược lại, “nhổ” các quả bóng ra.
Khi một quả bóng bay bị hút vào, tất cả các quả bóng bay ở bên phải của quả bóng bị hút đều bị dịch chuyển sang trái. "Nhổ ra" quả bóng có thể nằm giữa hai quả bóng bất kỳ (và cả trước quả bóng đầu tiên hoặc sau quả bóng cuối cùng), sau đó quả bóng nhổ được đưa vào giữa những quả bóng này và tất cả các quả bóng ở bên phải của quả bóng được chèn đều được dịch chuyển sang bên phải .
Có thể hút nhiều hơn một quả bóng vào thiết bị cùng một lúc và khi nhổ quả bóng ra, quả bóng bị hút cuối cùng sẽ được nhổ ra trước, sau đó là quả bóng áp chót, v.v. (tức là thiết bị hoạt động theo nguyên tắc ngăn xếp). Các quả bóng được nhổ ra cùng một lúc, tức là bạn chỉ có thể nhổ một quả bóng, để phần còn lại bên trong thiết bị (trong trường hợp này, bạn có thể tiếp tục “nhổ” các quả bóng vào chỗ cũ hoặc ở một nơi khác hoặc hút các quả bóng mới).
Hoạt động tiêu tốn nhiều năng lượng nhất trong số các hoạt động được mô tả là hoạt động hút quả bóng, vì vậy chúng tôi muốn giảm thiểu số lượng các hoạt động như vậy.
Viết một chương trình, với cách sắp xếp ban đầu của các quả bóng, sẽ xác định số lần hút tối thiểu cần thiết để sắp xếp các quả bóng theo thứ tự số.
Đầu vào
Trong tệp đầu vào, số N được đưa ra đầu tiên — số bóng (1≤N≤1000). Sau đó, có N số cung cấp số quả bóng theo thứ tự từ trái sang phải ở vị trí hiện tại của chúng (mỗi số — từ 1 đến N và mỗi số xuất hiện đúng một lần trong chuỗi).
Đầu ra
Xuất một số duy nhất — số lần hút bóng tối thiểu cần thiết để sắp xếp các quả bóng theo thứ tự số lượng của chúng.
Nhận xét về thử nghiệm mẫu
1.Bạn có thể hút, chẳng hạn như quả bóng số 2 và nhổ nó ra giữa quả bóng thứ 1 và thứ 3.
2.>Bạn có thể làm điều gì đó như thế này. Đầu tiên,
hút quả bóng bay số 1, sau đó – quả bóng số 2. Sau đó, chúng ta di chuyển về đầu và nhổ quả bóng ra trước quả bóng thứ 4 (đây sẽ là quả bóng số 2). Tiếp theo, hút quả bóng bay số 3 và nhổ nó ra giữa quả bóng bay số 2 và số 4. Sau đó, di chuyển đến đầu và nhổ quả bóng bay số 1. Tuy nhiên, đây không phải là thứ tự duy nhất có thể có của các quả bóng bay trong ví dụ này.
| Đầu vào |
Đầu ra |
|
3
2 1 3
|
1 |
|
4
4 3 2 1
|
3 |
Olympic đồng đội, Olympic đồng đội Moscow, lớp 9-11, 2007, Giải A, Vấn đề F