| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 76 | 64 | 56 | 88.889% |
We have a strange box with a big red button. There is a sequence of integers in the box. Whenever we push the big red button, the sequence in the box changes. We call the box a “copier”, because the new sequence is created from the old one by copying some contiguous section.
More precisely, each time the red button is pushed the copier does the following: Suppose that the current sequence in the box is a0, a1, a2, …, am − 1. The copier chooses some i, j, k such that 0 ≤ i < j ≤ k ≤ m. Then the copier inserts a copy of ai, …, aj − 1 immediately after ak − 1. Note that j ≤ k: the copy is always inserted to the right of the original. Here is how the sequence looks like after the insertion:
$$ a_0, \dots, a_{i-1}, \underbrace{a_i, \dots, a_{j-1}}_{\rm original}, a_j, \dots, a_{k-1}, \underbrace{a_i, \dots, a_{j-1}}_{\rm copy}, a_k, \dots, a_{m-1} $$
In the morning we had some permutation of 1…l in the box. Then we pushed the button zero or more times. Each time we pushed the button, a new (not necessarily different) triple (i, j, k) was chosen and the sequence was modified as described above. You are given the sequence S that was in the copier at the end of the day. Reconstruct the original permutation.
The first line of the input file contains an integer t ≤ 60 specifying the number of test cases. Each test case is preceded by a blank line.
Each test case consists of two lines. The first line contains an integer n (3 ≤ n ≤ 100 000) – the length of the final sequence S. The second line contains n integers – the sequence S. For each test case, there is a positive integer l such that S can be produced from some permutation of {1, 2, …, l} using a finite sequence of copier operations.
For each test case, output a single line with a space-separated list of integers: the original permutation. If there are multiple valid solutions, output any of them.
| 번호 | 배점 | 제한 |
|---|---|---|
| Easy | 1 | You may also assume that n ≤ 10 000, that the sequence S was obtained from some permutation by pushing the red button exactly once, and that the copier chose j = k, i.e., it inserted the copied subsequence immediately after the original. |
| Hard | 2 |
3 7 5 1 4 1 4 2 3 11 4 3 1 2 3 1 4 3 3 1 4 7 1 1 1 1 1 1 1
5 1 4 2 3 4 3 1 2 1
The first test case satisfies the conditions for the easy subproblem, the copier duplicated the subsequence 1 4. In the second test case we started with 4 3 1 2, changed it into (4 3) 1 2 (4 3), then changed that sequence into 4 (3 1) 2 (3 1) 4 3, and finally changed that into 4 3 1 2 (3 1 4) 3 (3 1 4).