P16534 [THUPC 2026 Final] Yearbook Sorting

From the finals of the 2026 Tsinghua University Student Programming Contest and Collegiate Invitational (THUPC2026). Resources such as editorials can be found at https://github.com/dapingguo8/THUPC2026-final. > The tea party was nearing its end. As a special nostalgic event for the 10th anniversary celebration, Little T deliberately brought out the precious archives of past THUPC contests—a row of contest yearbooks recording bits and pieces of the past ten years—for everyone to read. > > After reading, the two of them were going to put the yearbooks back on the shelf. As time had passed, the degree of damage of the yearbooks varied. Careful Little S suggested that, when putting them back, they should be reordered in strictly increasing order of damage, so that the traces of time could be shown more clearly. However, the paper of the yearbooks was already very fragile: each time, they could only move one yearbook forward by one position extremely carefully, and this would inevitably slightly increase the damage of that yearbook. What was worse, the time left for sorting was very limited. Little S wanted to know whether it was possible, within a limited number of operations, to put these yearbooks back on the shelf and make them neatly ordered.

There are $n$ yearbooks on the shelf. Initially, the damage of the $i$-th ($1 \le i \le n$) yearbook is $a_i$. In each move, you must first choose a position $p$ ($1 \le p \le n - 1$), then move the $(p + 1)$-th yearbook forward to be in front of the $p$-th yearbook. After the move, its damage will increase by $1$. Due to limited time, you can make at most $n ^ 2 - n$ moves in total. As one of the many participants who read the yearbooks, you need to help Little S plan a specific sequence of moves so that, in the end, the damages of the yearbooks on the shelf are **strictly increasing** from left to right.

Each test contains multiple sets of testdata. The first line contains a positive integer $T$ ($1 \le T \le 10$), which is the number of test cases. For each test case: - The first line contains a positive integer $n$ ($1 \le n \le 500$), the number of yearbooks. - The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), representing the initial damage of each yearbook.

For each test case, if there exists a feasible sequence of moves: - Output a non-negative integer $k$ ($0 \le k \le n ^ 2 - n$) in the first line, representing the number of moves. - Output $k$ positive integers $p_1, p_2, \dots, p_k$ ($1 \le p_i \le n - 1$) in the second line, representing the chosen position in each move. If it is impossible to make the final damages strictly increasing from left to right, output only one line containing an integer $-1$.

- For the first test case, the sequence $[1,2]$ is already strictly increasing. - For the second test case, it is impossible to turn the sequence $[2,1]$ into a strictly increasing sequence within the allowed number of steps. - For the third test case, first choose index $2$ to change the sequence to $[4,2,5]$; then choose index $1$ to change the sequence to $[3,4,5]$. Translated by ChatGPT 5