1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Delicate Anti-monotonous Operations
Contest: Good Bye 2024: 2025 is NEAR
Difficulty rating: 3500
Tags: constructive algorithms, implementation

There are always many repetitive tasks in life. Iris always dislikes them, so she refuses to repeat them. However, time cannot be turned back; we only have to move forward.

Formally, Iris has an integer sequence $$$a_1, a_2, \ldots, a_n$$$, where each number in the sequence is between $$$1$$$ and $$$w$$$, inclusive. It is guaranteed that $$$w \geq 2$$$.

Iris defines an operation as selecting two numbers $$$a_i, a_{i+1}$$$ satisfying $$$a_i = a_{i+1}$$$, and then changing them to two arbitrary integers within the range $$$[1, w]$$$. Iris does not like equality, so she must guarantee that $$$a_i \neq a_{i+1}$$$ after the operation. Two identical pairs $$$a_i, a_{i+1}$$$ can be selected multiple times.

Iris wants to know the maximum possible sum of all elements of $$$a$$$ after several (possible, zero) operations, as well as the minimum number of operations required to achieve this maximum value.

Input format:
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$w$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$, $$$2 \leq w \leq 10^8$$$) — the length of the array, and the maximum allowed value of the elements.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq w$$$) — the elements in the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, output two integers — the maximum possible sum of all elements of $$$a$$$ and the minimum number of operations required, respectively.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case, no operation can be performed so the answers are $$$\sum a_i = 15$$$ and $$$0$$$, respectively.

In the second test case, the operations can be performed as follows:

$$$$$$[3, 1, 2, 3, 4, \underline{1, 1}] \rightarrow [3, 1, 2, 3, \underline{4, 4}, 5] \rightarrow [3, 1, 2, \underline{3, 3}, 5, 5] \rightarrow [3, 1, \underline{2, 2}, 5, 5, 5] \rightarrow [3, \underline{1, 1}, 5, 5, 5, 5] \rightarrow [\underline{3, 3}, 5, 5, 5, 5, 5] \rightarrow [4, 5, 5, 5, 5, 5, 5]$$$$$$

It can be shown this is optimal, so we should output $$$\sum a_i = 34$$$ and the number of operations, $$$6$$$, respectively.

Example input:
2
5 8
1 2 3 4 5
7 5
3 1 2 3 4 1 1

Example output:
15 0
34 6

Editorial:
Cards Partition
Contest: Codeforces Round 975 (Div. 1)
Difficulty rating: 1600
Tags: 2-sat, brute force, greedy, implementation, math

You have some cards. An integer between $$$1$$$ and $$$n$$$ is written on each card: specifically, for each $$$i$$$ from $$$1$$$ to $$$n$$$, you have $$$a_i$$$ cards which have the number $$$i$$$ written on them.

There is also a shop which contains unlimited cards of each type. You have $$$k$$$ coins, so you can buy at most $$$k$$$ new cards in total, and the cards you buy can contain any integer between $$$\mathbf{1}$$$ and $$$\mathbf{n}$$$, inclusive.

After buying the new cards, you must partition all your cards into decks, according to the following rules:

- all the decks must have the same size;
- there are no pairs of cards with the same value in the same deck.

Find the maximum possible size of a deck after buying cards and partitioning them optimally.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$, $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq 10^{16}$$$) — the number of distinct types of cards and the number of coins.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^{10}$$$, $$$\sum a_i \geq 1$$$) — the number of cards of type $$$i$$$ you have at the beginning, for each $$$1 \leq i \leq n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer: the maximum possible size of a deck if you operate optimally.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, you can buy one card with the number $$$1$$$, and your cards become $$$[1, 1, 1, 1, 2, 2, 3, 3]$$$. You can partition them into the decks $$$[1, 2], [1, 2], [1, 3], [1, 3]$$$: they all have size $$$2$$$, and they all contain distinct values. You can show that you cannot get a partition with decks of size greater than $$$2$$$, so the answer is $$$2$$$.

In the second test case, you can buy two cards with the number $$$1$$$ and one card with the number $$$3$$$, and your cards become $$$[1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5]$$$, which can be partitioned into $$$[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 2, 5], [2, 3, 5], [2, 4, 5]$$$. You can show that you cannot get a partition with decks of size greater than $$$3$$$, so the answer is $$$3$$$.

Example input:
9
3 1
3 2 2
5 4
2 6 1 2 4
2 100
1410065408 10000000000
10 8
7 4 6 6 9 3 10 2 8 7
2 12
2 2
2 70
0 1
1 0
1
3 0
2 1 2
3 1
0 3 3

Example output:
2
3
1
7
2
2
1
1
2

Editorial:
Speedbreaker
Contest: Codeforces Round 975 (Div. 1)
Difficulty rating: 1900
Tags: binary search, data structures, dp, greedy, implementation, two pointers

There are $$$n$$$ cities in a row, numbered $$$1, 2, \ldots, n$$$ left to right.

- At time $$$1$$$, you conquer exactly one city, called the starting city.
- At time $$$2, 3, \ldots, n$$$, you can choose a city adjacent to the ones conquered so far and conquer it.

You win if, for each $$$i$$$, you conquer city $$$i$$$ at a time no later than $$$a_i$$$. A winning strategy may or may not exist, also depending on the starting city. How many starting cities allow you to win?

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of cities.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the deadlines for conquering the cities.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer: the number of starting cities that allow you to win.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, cities $$$2$$$, $$$3$$$, and $$$4$$$ are good starting cities.

In the second test case, there are no good starting cities.

In the third test case, the only good starting city is city $$$5$$$.

Example input:
3
6
6 3 3 3 5 5
6
5 6 4 1 4 5
9
8 6 4 2 1 3 5 7 9

Example output:
3
0
1

Editorial:
Tree Pruning
Contest: Codeforces Round 975 (Div. 1)
Difficulty rating: 1700
Tags: brute force, dfs and similar, greedy, sortings, trees

You are given a tree with $$$n$$$ nodes, rooted at node $$$1$$$. In this problem, a leaf is a non-root node with degree $$$1$$$.

In one operation, you can remove a leaf and the edge adjacent to it (possibly, new leaves appear). What is the minimum number of operations that you have to perform to get a tree, also rooted at node $$$1$$$, where all the leaves are at the same distance from the root?

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$3 \leq n \leq 5 \cdot 10^5$$$) — the number of nodes.

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$, $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$), describing an edge that connects $$$u$$$ and $$$v$$$. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output format:
For each test case, output a single integer: the minimum number of operations needed to achieve your goal.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first two examples, the tree is as follows:

In the first example, by removing edges $$$(1, 3)$$$ and $$$(2, 5)$$$, the resulting tree has all leaves (nodes $$$6$$$ and $$$7$$$) at the same distance from the root (node $$$1$$$), which is $$$3$$$. The answer is $$$2$$$, as it is the minimum number of edges that need to be removed to achieve the goal.

In the second example, removing edges $$$(1, 4)$$$ and $$$(5, 7)$$$ results in a tree where all leaves (nodes $$$4$$$ and $$$5$$$) are at the same distance from the root (node $$$1$$$), which is $$$2$$$.

Example input:
3
7
1 2
1 3
2 4
2 5
4 6
4 7
7
1 2
1 3
1 4
2 5
3 6
5 7
15
12 9
1 6
6 14
9 11
8 7
3 5
13 5
6 10
13 15
13 6
14 12
7 2
8 1
1 4

Example output:
2
2
5

Editorial:
Max Plus Min Plus Size
Contest: Codeforces Round 975 (Div. 1)
Difficulty rating: 2200
Tags: data structures, dp, dsu, greedy, implementation, matrices, sortings

You are given an array $$$a_1, a_2, \ldots, a_n$$$ of positive integers.

You can color some elements of the array red, but there cannot be two adjacent red elements (i.e., for $$$1 \leq i \leq n-1$$$, at least one of $$$a_i$$$ and $$$a_{i+1}$$$ must not be red).

Your score is the maximum value of a red element, plus the minimum value of a red element, plus the number of red elements. Find the maximum score you can get.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the given array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer: the maximum possible score you can get after coloring some elements red according to the statement.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, you can color the array as follows: $$$[\color{red}{5}, 4, \color{red}{5}]$$$. Your score is $$$\max([5, 5]) + \min([5, 5]) + \text{size}([5, 5]) = 5+5+2 = 12$$$. This is the maximum score you can get.

In the second test case, you can color the array as follows: $$$[4, \color{red}{5}, 4]$$$. Your score is $$$\max([5]) + \min([5]) + \text{size}([5]) = 5+5+1 = 11$$$. This is the maximum score you can get.

In the third test case, you can color the array as follows: $$$[\color{red}{3}, 3, \color{red}{3}, 3, \color{red}{4}, 1, 2, \color{red}{3}, 5, \color{red}{4}]$$$. Your score is $$$\max([3, 3, 4, 3, 4]) + \min([3, 3, 4, 3, 4]) + \text{size}([3, 3, 4, 3, 4]) = 4+3+5 = 12$$$. This is the maximum score you can get.

Example input:
4
3
5 4 5
3
4 5 4
10
3 3 3 3 4 1 2 3 5 4
10
17 89 92 42 29 41 92 14 70 45

Example output:
12
11
12
186

Editorial:
Complex Segments (Easy Version)
Contest: Codeforces Round 975 (Div. 1)
Difficulty rating: 3300
Tags: binary search, data structures, divide and conquer, dsu, greedy, math, sortings

This is the easy version of the problem. In this version, the constraints on $$$n$$$ and the time limit are lower. You can make hacks only if both versions of the problem are solved.

A set of (closed) segments is complex if it can be partitioned into some subsets such that

- all the subsets have the same size; and
- a pair of segments intersects if and only if the two segments are in the same subset.

You are given $$$n$$$ segments $$$[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$$$. Find the maximum size of a complex subset of these segments.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^4$$$) — the number of segments.

The second line of each test case contains $$$n$$$ integers $$$l_1, l_2, \ldots, l_n$$$ ($$$1 \le l_i \le 2n$$$) — the left endpoints of the segments.

The third line of each test case contains $$$n$$$ integers $$$r_1, r_2, \ldots, r_n$$$ ($$$l_i \leq r_i \le 2n$$$) — the right endpoints of the segments.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^4$$$.

Output format:
For each test case, output a single integer: the maximum size of a complex subset of the given segments.

Constraints:
Time limit: 6.0 s
Memory limit: 256.0 MB

Note:
In the first test case, all pairs of segments intersect, therefore it is optimal to form a single group containing all of the three segments.

In the second test case, there is no valid partition for all of the five segments. A valid partition with four segments is the following: $$$\{\{ [1, 5], [2, 4] \}, \{ [6, 9], [8, 10] \}\}$$$.

In the third test case, it is optimal to make a single group containing all the segments except the second.

Example input:
3
3
1 2 3
5 4 6
5
1 2 3 6 8
5 4 7 9 10
5
3 1 4 1 5
7 2 6 5 10

Example output:
3
4
4

Editorial:
Complex Segments (Hard Version)
Contest: Codeforces Round 975 (Div. 1)
Difficulty rating: 3400
Tags: binary search, data structures, divide and conquer, dsu, greedy, math, sortings

This is the hard version of the problem. In this version, the constraints on $$$n$$$ and the time limit are higher. You can make hacks only if both versions of the problem are solved.

A set of (closed) segments is complex if it can be partitioned into some subsets such that

- all the subsets have the same size; and
- a pair of segments intersects if and only if the two segments are in the same subset.

You are given $$$n$$$ segments $$$[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$$$. Find the maximum size of a complex subset of these segments.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of segments.

The second line of each test case contains $$$n$$$ integers $$$l_1, l_2, \ldots, l_n$$$ ($$$1 \le l_i \le 2n$$$) — the left endpoints of the segments.

The third line of each test case contains $$$n$$$ integers $$$r_1, r_2, \ldots, r_n$$$ ($$$l_i \leq r_i \le 2n$$$) — the right endpoints of the segments.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, output a single integer: the maximum size of a complex subset of the given segments.

Constraints:
Time limit: 13.0 s
Memory limit: 256.0 MB

Note:
In the first test case, all pairs of segments intersect, therefore it is optimal to form a single group containing all of the three segments.

In the second test case, there is no valid partition for all of the five segments. A valid partition with four segments is the following: $$$\{\{ [1, 5], [2, 4] \}, \{ [6, 9], [8, 10] \}\}$$$.

In the third test case, it is optimal to make a single group containing all the segments except the second.

Example input:
3
3
1 2 3
5 4 6
5
1 2 3 6 8
5 4 7 9 10
5
3 1 4 1 5
7 2 6 5 10

Example output:
3
4
4

Editorial:
Penchick and Modern Monument
Contest: Codeforces Round 987 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, dp, greedy, math

Amidst skyscrapers in the bustling metropolis of Metro Manila, the newest Noiph mall in the Philippines has just been completed! The construction manager, Penchick, ordered a state-of-the-art monument to be built with $$$n$$$ pillars.

The heights of the monument's pillars can be represented as an array $$$h$$$ of $$$n$$$ positive integers, where $$$h_i$$$ represents the height of the $$$i$$$-th pillar for all $$$i$$$ between $$$1$$$ and $$$n$$$.

Penchick wants the heights of the pillars to be in non-decreasing order, i.e. $$$h_i \le h_{i + 1}$$$ for all $$$i$$$ between $$$1$$$ and $$$n - 1$$$. However, due to confusion, the monument was built such that the heights of the pillars are in non-increasing order instead, i.e. $$$h_i \ge h_{i + 1}$$$ for all $$$i$$$ between $$$1$$$ and $$$n - 1$$$.

Luckily, Penchick can modify the monument and do the following operation on the pillars as many times as necessary:

- Modify the height of a pillar to any positive integer. Formally, choose an index $$$1\le i\le n$$$ and a positive integer $$$x$$$. Then, assign $$$h_i := x$$$.

Help Penchick determine the minimum number of operations needed to make the heights of the monument's pillars non-decreasing.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 50$$$) — the number of pillars.

The second line of each test case contains $$$n$$$ integers $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le n$$$ and $$$h_i\ge h_{i+1}$$$) — the height of the pillars.

Please take note that the given array $$$h$$$ is non-increasing.

Note that there are no constraints on the sum of $$$n$$$ over all test cases.

Output format:
For each test case, output a single integer representing the minimum number of operations needed to make the heights of the pillars non-decreasing.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the initial heights of pillars are $$$h = [5, 4, 3, 2, 1]$$$.

- In the first operation, Penchick changes the height of pillar $$$1$$$ to $$$h_1 := 2$$$.
- In the second operation, he changes the height of pillar $$$2$$$ to $$$h_2 := 2$$$.
- In the third operation, he changes the height of pillar $$$4$$$ to $$$h_4 := 4$$$.
- In the fourth operation, he changes the height of pillar $$$5$$$ to $$$h_5 := 4$$$.

After the operation, the heights of the pillars are $$$h = [2, 2, 3, 4, 4]$$$, which is non-decreasing. It can be proven that it is not possible for Penchick to make the heights of the pillars non-decreasing in fewer than $$$4$$$ operations.

In the second test case, Penchick can make the heights of the pillars non-decreasing by modifying the height of pillar $$$3$$$ to $$$h_3 := 2$$$.

In the third test case, the heights of pillars are already non-decreasing, so no operations are required.

Example input:
3
5
5 4 3 2 1
3
2 2 1
1
1

Example output:
4
1
0

Editorial:
Penchick and Satay Sticks
Contest: Codeforces Round 987 (Div. 2)
Difficulty rating: 900
Tags: brute force, greedy, sortings

Penchick and his friend Kohane are touring Indonesia, and their next stop is in Surabaya!

In the bustling food stalls of Surabaya, Kohane bought $$$n$$$ satay sticks and arranged them in a line, with the $$$i$$$-th satay stick having length $$$p_i$$$. It is given that $$$p$$$ is a permutation$$$^{\text{∗}}$$$ of length $$$n$$$.

Penchick wants to sort the satay sticks in increasing order of length, so that $$$p_i=i$$$ for each $$$1\le i\le n$$$. For fun, they created a rule: they can only swap neighboring satay sticks whose lengths differ by exactly $$$1$$$. Formally, they can perform the following operation any number of times (including zero):

- Select an index $$$i$$$ ($$$1\le i\le n-1$$$) such that $$$|p_{i+1}-p_i|=1$$$;
- Swap $$$p_i$$$ and $$$p_{i+1}$$$.

Determine whether it is possible to sort the permutation $$$p$$$, thus the satay sticks, by performing the above operation.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2\cdot 10^5$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — the number of satay sticks.

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — the permutation $$$p$$$ representing the length of the satay sticks.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, output "YES" if it is possible to sort permutation $$$p$$$ by performing the operation. Otherwise, output "NO".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
In the first test case, we can sort permutation $$$p = [2, 1, 3, 4]$$$ by performing an operation on index $$$1$$$ ($$$|p_2 - p_1| = |1 - 2| = 1$$$), resulting in $$$p = [1, 2, 3, 4]$$$.

In the second test case, it can be proven that it is impossible to sort permutation $$$p = [4, 2, 3, 1]$$$ by performing the operation. Here is an example of a sequence of operations that can be performed on the permutation:

- Select $$$i = 2$$$ ($$$|p_3 - p_2| = |3 - 2| = 1$$$). This results in $$$p = [4, 3, 2, 1]$$$.
- Select $$$i = 1$$$ ($$$|p_2 - p_1| = |3 - 4| = 1$$$). This results in $$$p = [3, 4, 2, 1]$$$.
- Select $$$i = 3$$$ ($$$|p_4 - p_3| = |1 - 2| = 1$$$). This results in $$$p = [3, 4, 1, 2]$$$.

Unfortunately, permutation $$$p$$$ remains unsorted after performing the operations.

Example input:
2
4
2 1 3 4
4
4 2 3 1

Example output:
YES
NO

Editorial:
Penchick and BBQ Buns
Contest: Codeforces Round 987 (Div. 2)
Difficulty rating: 1300
Tags: constructive algorithms, math, number theory

Penchick loves two things: square numbers and Hong Kong-style BBQ buns! For his birthday, Kohane wants to combine them with a gift: $$$n$$$ BBQ buns arranged from left to right. There are $$$10^6$$$ available fillings of BBQ buns, numbered from $$$1$$$ to $$$10^6$$$. To ensure that Penchick would love this gift, Kohane has a few goals:

- No filling is used exactly once; that is, each filling must either not appear at all or appear at least twice.
- For any two buns $$$i$$$ and $$$j$$$ that have the same filling, the distance between them, which is $$$|i-j|$$$, must be a perfect square$$$^{\text{∗}}$$$.

Help Kohane find a valid way to choose the filling of the buns, or determine if it is impossible to satisfy her goals! If there are multiple solutions, print any of them.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2\cdot 10^5$$$). The description of the test cases follows.

The only line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — the number of BBQ buns.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, if no valid choice of fillings exists, output $$$-1$$$. Otherwise, output $$$n$$$ integers, where the $$$i$$$-th integer represents the filling of the $$$i$$$-th BBQ bun. If there are multiple solutions, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the choice of fillings "1 1 1" is not allowed because buns $$$1$$$ and $$$3$$$ have the same filling, but are distance $$$2$$$ apart, which is not a perfect square. The choice of fillings "1 1 2" is also not allowed as filling $$$2$$$ is only used once.

In the second test case, the solution is valid because no filling is used exactly once, and any two buns with the same filling are spaced at a distance equal to a perfect square. For example, buns $$$1$$$ and $$$10$$$ both have filling $$$1$$$ and are spaced at a distance of $$$9=3^2$$$. Similarly, buns $$$5$$$ and $$$9$$$ both have filling $$$10$$$ and are spaced at a distance of $$$4=2^2$$$.

Example input:
2
3
12

Example output:
-1
1 2 3 6 10 2 7 6 10 1 7 3

Editorial: