SpCipher | Logout
You have +256! Wow!
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP RAYAN
PROBLEMS SUBMIT CODE MY SUBMISSIONS STATUS HACKS STANDINGS CUSTOM INVOCATION
Codeforces Round 834 (Div. 3)
G. Restore the Permutation Finished
time limit per test: 1 second
Practice
memory limit per test: 256 megabytes
A sequence of n numbers is called permutation if it contains all numbers from 1 to n exactly once. For example, the sequences [
3, 1, 4, 2 ], [1 ] and [2, 1 ] are permutations, but [1, 2, 1 ], [0, 1 ] and [1, 3, 4 ] — are not.
→ Virtual participation
For a permutation p of even length n you can make an array b of length n2 such that:
Virtual contest is a way to take part in past
n
bi = max(p2i−1 , p2i ) for 1 ≤ i ≤ 2
contest, as close as possible to participation
on time. It is supported only ICPC mode for
virtual contests. If you've seen these
For example, if p = [2, 4, 3, 1, 5, 6], then:
problems, a virtual contest is not for you -
solve these problems in the archive. If you
b1 = max(p1 , p2 ) = max(2, 4) = 4 just want to solve some problem from a
b2 = max(p3 , p4 ) = max(3, 1) = 3 contest, a virtual contest is not for you -
solve this problem in the archive. Never use
b3 = max(p5 , p6 ) = max(5, 6) = 6 someone else's code, read the tutorials or
communicate with other person during a
As a result, we made b = [4, 3, 6]. virtual contest.
For a given array b , find the lexicographically minimal permutation p such that you can make the given array b from it.
Start virtual contest
If b = [4, 3, 6 ], then the lexicographically minimal permutation from which it can be made is p = [1, 4, 2, 3, 5, 6], since:
b1 = max(p1 , p2 ) = max(1, 4) = 4 → Clone Contest to Mashup
b2 = max(p3 , p4 ) = max(2, 3) = 3
b3 = max(p5 , p6 ) = max(5, 6) = 6 You can clone this contest to a mashup.
A permutation x 1 , x 2 , … , x n is lexicographically smaller than a permutation y1 , y2 … , yn if and only if there exists such i ( Clone Contest
1 ≤ i ≤ n ) that x1 = y1 , x2 = y2 , … , xi−1 = yi−1 and xi < yi .
Input → Submit?
4
The first line of input data contains a single integer t (1 ≤ t ≤ 10 ) — the number of test cases.
The description of the test cases follows. Language: GNU G++17 7.3.0
Choose
The first line of each test case contains one even integer n (2 ≤ n ≤ 2 ⋅ 105 ). file:
Choose File no file selected
The second line of each test case contains exactly n2 integers bi (1 ≤ bi ≤ n ) — elements of array b . Submit
It is guaranteed that the sum of n values over all test cases does not exceed 2 ⋅ 105 .
Output → Contest materials
For each test case, print on a separate line:
Announcement
lexicographically minimal permutation p such that you can make an array b from it;
Tutorial
or a number -1 if the permutation you are looking for does not exist.
Example
input Copy
6
6
4 3 6
4
2 4
8
8 7 2 3
6
6 4 2
4
4 4
8
8 7 4 5
output Copy
1 4 2 3 5 6
1 2 3 4
-1
5 6 3 4 1 2
-1
1 8 6 7 2 4 3 5
Note
The first test case is parsed in the problem statement.
Codeforces (c) Copyright 2010-2025 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Oct/24/2025 01:16:04UTC+5.5 (j1).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by