P16919 [JLCPC 2026] Koishi Komeiji Is the Best in the World

Koishi picked up a positive integer sequence $a = [a_1, a_2, \cdots, a_n]$ of length $n$ on the road, where $1\le a_i\le n$. Now Koishi computed the **prefix maximum sequence** $b = [b_1, b_2, \cdots, b_n]$ of $a$, where $b_i$ denotes the maximum among the first $i$ elements of $a$, i.e. $$b_i = \max\{a_1, a_2, \cdots, a_i\} = \max_{1\le j\le i}\{a_j\}$$ After obtaining the two sequences, Koishi mixed them together: define a sequence $c$ of length $2n$ as $c = [a_1, a_2, \cdots, a_n, b_1, b_2, \cdots, b_n]$, and then **sorted** $c$ **in non-decreasing order**. Because Koishi is an unconscious girl, she lost the values of $a$ and $b$, leaving only the sequence $c$. Because Koishi is an unconscious girl, she gave you the sequence $c$—the cutest college student of the 21st century—hoping that you can find any valid sequence $a$. There may be multiple valid sequences $a$; in that case, you only need to output any one of them. There may also be no valid sequence $a$ at all; in that case, you need to report that there is no solution.

The first line contains an integer $T$, denoting the number of test cases. Then follow $T$ test cases, each described as follows: - The first line contains an integer $n$, the length of sequence $a$. - The second line contains a sequence $c$ of length $2 \times n$, where adjacent integers are separated by a single space. It is guaranteed that $c$ is non-decreasing, and $1\le c_i\le n$. It is guaranteed that $1\le \sum n\le 3\times 10^5$.

For each test case: - If there is a solution, output a string `Yes` on the first line, and output $n$ integers $[a_1, a_2, \cdots, a_n]$ on the second line, separated by single spaces, representing one valid sequence $a$ you found. - If there is no solution, output a single line with the string `No`. `Yes` and `No` are case-insensitive. For example, `Yes`, `YES`, and `yEs` are all considered affirmative, while `No`, `NO`, and `nO` are all considered negative.

Translated by ChatGPT 5