以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
Problem K
Book Sorting
Time limit: 2 seconds
You have n books arranged from left to right on a bookshelf. These books are uniquely labeled from 1 to n. The i-th
book from the left is labeled pi. You want to sort the books so that their labels are in ascending order from left to right.
In one step, you can perform one of the following actions:
• Choose two adjacent books and swap them.
• Choose one book and move it to the leftmost position.
• Choose one book and move it to the rightmost position.
Compute the minimum number of steps required to sort the books.
Input
The first line of input contains an integer n (2 ≤n ≤500 000). The second line contains n pairwise distinct integers
p1, p2, . . . , pn (1 ≤pi ≤n).
Output
Output the minimum number of steps to sort the books in ascending order from left to right by their labels.
Sample Input #1 Sample Output #1
6 3
6 2 1 4 3 5
Explanation for the sample input/output #1
You can do the following three steps in order: swap the books labeled 2 and 1, swap the books labeled 4 and 3, and
move the book labeled 6 to the rightmost position.
6 2 1 4 3 5 →6 1 2 4 3 5 →6 1 2 3 4 5 →1 2 3 4 5 6
It can be shown that two or fewer steps are insufficient to sort the books.
Sample Input #2 Sample Output #2
9 5
9 2 4 3 7 5 1 8 6
The 2025 ICPC Asia Pacific Championship Problem K: Book Sorting
This page is intentionally left blank.
The 2025 ICPC Asia Pacific Championship Problem K: Book Sorting