apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a_1, a_2, \dots, a_n$$$ where all $$$a_i$$$ are integers and greater than $$$0$$$.

In one operation, you can choose two different indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$). If $$$gcd(a_i, a_j)$$$ is equal to the minimum element of the whole array $$$a$$$, you can swap $$$a_i$$$ and $$$a_j$$$. $$$gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

Now you'd like to make $$$a$$$ non-decreasing using the operation any number of times (possibly zero). Determine if you can do this.

An array $$$a$$$ is non-decreasing if and only if $$$a_1 \le a_2 \le \ldots \le a_n$$$.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

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

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

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

## Output Format
For each test case, output "YES" if it is possible to make the array $$$a$$$ non-decreasing using the described operation, or "NO" if it is impossible to do so.

## Examples
```input
4
1
8
6
4 3 6 6 2 9
4
4 5 6 7
5
7 5 2 2 4
```
```output
YES
YES
YES
NO
```

## Note
In the first and third sample, the array is already non-decreasing.

In the second sample, we can swap $$$a_1$$$ and $$$a_3$$$ first, and swap $$$a_1$$$ and $$$a_5$$$ second to make the array non-decreasing.

In the forth sample, we cannot the array non-decreasing using the operation.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a tree that consists of $$$n$$$ nodes. You should label each of its $$$n-1$$$ edges with an integer in such way that satisfies the following conditions:

- each integer must be greater than $$$0$$$;
- the product of all $$$n-1$$$ numbers should be equal to $$$k$$$;
- the number of $$$1$$$-s among all $$$n-1$$$ integers must be minimum possible.

Let's define $$$f(u,v)$$$ as the sum of the numbers on the simple path from node $$$u$$$ to node $$$v$$$. Also, let $$$\sum\limits_{i=1}^{n-1} \sum\limits_{j=i+1}^n f(i,j)$$$ be a distribution index of the tree.

Find the maximum possible distribution index you can get. Since answer can be too large, print it modulo $$$10^9 + 7$$$.

In this problem, since the number $$$k$$$ can be large, the result of the prime factorization of $$$k$$$ is given instead.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

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

Each of the next $$$n-1$$$ lines describes an edge: the $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$) — indices of vertices connected by the $$$i$$$-th edge.

Next line contains a single integer $$$m$$$ ($$$1 \le m \le 6 \cdot 10^4$$$) — the number of prime factors of $$$k$$$.

Next line contains $$$m$$$ prime numbers $$$p_1, p_2, \ldots, p_m$$$ ($$$2 \le p_i < 6 \cdot 10^4$$$) such that $$$k = p_1 \cdot p_2 \cdot \ldots \cdot p_m$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$, the sum of $$$m$$$ over all test cases doesn't exceed $$$6 \cdot 10^4$$$, and the given edges for each test cases form a tree.

## Output Format
Print the maximum distribution index you can get. Since answer can be too large, print it modulo $$$10^9+7$$$.

## Examples
```input
3
4
1 2
2 3
3 4
2
2 2
4
3 4
1 3
3 2
2
3 2
7
6 1
2 3
4 6
7 3
5 1
3 6
4
7 5 13 3
```
```output
17
18
286
```

## Note
In the first test case, one of the optimal ways is on the following image:

In this case, $$$f(1,2)=1$$$, $$$f(1,3)=3$$$, $$$f(1,4)=5$$$, $$$f(2,3)=2$$$, $$$f(2,4)=4$$$, $$$f(3,4)=2$$$, so the sum of these $$$6$$$ numbers is $$$17$$$.

In the second test case, one of the optimal ways is on the following image:

In this case, $$$f(1,2)=3$$$, $$$f(1,3)=1$$$, $$$f(1,4)=4$$$, $$$f(2,3)=2$$$, $$$f(2,4)=5$$$, $$$f(3,4)=3$$$, so the sum of these $$$6$$$ numbers is $$$18$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 384.0 MB

# Problem
There is a square of size $$$10^6 \times 10^6$$$ on the coordinate plane with four points $$$(0, 0)$$$, $$$(0, 10^6)$$$, $$$(10^6, 0)$$$, and $$$(10^6, 10^6)$$$ as its vertices.

You are going to draw segments on the plane. All segments are either horizontal or vertical and intersect with at least one side of the square.

Now you are wondering how many pieces this square divides into after drawing all segments. Write a program calculating the number of pieces of the square.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$0 \le n, m \le 10^5$$$) — the number of horizontal segments and the number of vertical segments.

The next $$$n$$$ lines contain descriptions of the horizontal segments. The $$$i$$$-th line contains three integers $$$y_i$$$, $$$lx_i$$$ and $$$rx_i$$$ ($$$0 < y_i < 10^6$$$; $$$0 \le lx_i < rx_i \le 10^6$$$), which means the segment connects $$$(lx_i, y_i)$$$ and $$$(rx_i, y_i)$$$.

The next $$$m$$$ lines contain descriptions of the vertical segments. The $$$i$$$-th line contains three integers $$$x_i$$$, $$$ly_i$$$ and $$$ry_i$$$ ($$$0 < x_i < 10^6$$$; $$$0 \le ly_i < ry_i \le 10^6$$$), which means the segment connects $$$(x_i, ly_i)$$$ and $$$(x_i, ry_i)$$$.

It's guaranteed that there are no two segments on the same line, and each segment intersects with at least one of square's sides.

## Output Format
Print the number of pieces the square is divided into after drawing all the segments.

## Examples
```input
3 3
2 3 1000000
4 0 4
3 0 1000000
4 0 1
2 0 5
3 1 1000000
```
```output
7
```

## Note
The sample is like this:

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ of length $$$2^n$$$. You should process $$$q$$$ queries on it. Each query has one of the following $$$4$$$ types:

1. $$$Replace(x, k)$$$ — change $$$a_x$$$ to $$$k$$$;
2. $$$Reverse(k)$$$ — reverse each subarray $$$[(i-1) \cdot 2^k+1, i \cdot 2^k]$$$ for all $$$i$$$ ($$$i \ge 1$$$);
3. $$$Swap(k)$$$ — swap subarrays $$$[(2i-2) \cdot 2^k+1, (2i-1) \cdot 2^k]$$$ and $$$[(2i-1) \cdot 2^k+1, 2i \cdot 2^k]$$$ for all $$$i$$$ ($$$i \ge 1$$$);
4. $$$Sum(l, r)$$$ — print the sum of the elements of subarray $$$[l, r]$$$.

Write a program that can quickly process given queries.

## Input Format
The first line contains two integers $$$n$$$, $$$q$$$ ($$$0 \le n \le 18$$$; $$$1 \le q \le 10^5$$$) — the length of array $$$a$$$ and the number of queries.

The second line contains $$$2^n$$$ integers $$$a_1, a_2, \ldots, a_{2^n}$$$ ($$$0 \le a_i \le 10^9$$$).

Next $$$q$$$ lines contains queries — one per line. Each query has one of $$$4$$$ types:

- "$$$1$$$ $$$x$$$ $$$k$$$" ($$$1 \le x \le 2^n$$$; $$$0 \le k \le 10^9$$$) — $$$Replace(x, k)$$$;
- "$$$2$$$ $$$k$$$" ($$$0 \le k \le n$$$) — $$$Reverse(k)$$$;
- "$$$3$$$ $$$k$$$" ($$$0 \le k < n$$$) — $$$Swap(k)$$$;
- "$$$4$$$ $$$l$$$ $$$r$$$" ($$$1 \le l \le r \le 2^n$$$) — $$$Sum(l, r)$$$.

It is guaranteed that there is at least one $$$Sum$$$ query.

## Output Format
Print the answer for each $$$Sum$$$ query.

## Examples
```input
2 3
7 4 9 9
1 2 8
3 1
4 2 4
```
```output
24
```
-----
```input
3 8
7 0 8 8 7 1 5 2
4 3 7
2 1
3 2
4 1 6
2 3
1 5 16
4 8 8
3 0
```
```output
29
22
1
```

## Note
In the first sample, initially, the array $$$a$$$ is equal to $$$\{7,4,9,9\}$$$.

After processing the first query. the array $$$a$$$ becomes $$$\{7,8,9,9\}$$$.

After processing the second query, the array $$$a_i$$$ becomes $$$\{9,9,7,8\}$$$

Therefore, the answer to the third query is $$$9+7+8=24$$$.

In the second sample, initially, the array $$$a$$$ is equal to $$$\{7,0,8,8,7,1,5,2\}$$$. What happens next is:

1. $$$Sum(3, 7)$$$ $$$\to$$$ $$$8 + 8 + 7 + 1 + 5 = 29$$$;
2. $$$Reverse(1)$$$ $$$\to$$$ $$$\{0,7,8,8,1,7,2,5\}$$$;
3. $$$Swap(2)$$$ $$$\to$$$ $$$\{1,7,2,5,0,7,8,8\}$$$;
4. $$$Sum(1, 6)$$$ $$$\to$$$ $$$1 + 7 + 2 + 5 + 0 + 7 = 22$$$;
5. $$$Reverse(3)$$$ $$$\to$$$ $$$\{8,8,7,0,5,2,7,1\}$$$;
6. $$$Replace(5, 16)$$$ $$$\to$$$ $$$\{8,8,7,0,16,2,7,1\}$$$;
7. $$$Sum(8, 8)$$$ $$$\to$$$ $$$1$$$;
8. $$$Swap(0)$$$ $$$\to$$$ $$$\{8,8,0,7,2,16,1,7\}$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Let $$$p$$$ be any permutation of length $$$n$$$. We define the fingerprint $$$F(p)$$$ of $$$p$$$ as the sorted array of sums of adjacent elements in $$$p$$$. More formally,

$$$$$$F(p)=\mathrm{sort}([p_1+p_2,p_2+p_3,\ldots,p_{n-1}+p_n]).$$$$$$

For example, if $$$n=4$$$ and $$$p=[1,4,2,3],$$$ then the fingerprint is given by $$$F(p)=\mathrm{sort}([1+4,4+2,2+3])=\mathrm{sort}([5,6,5])=[5,5,6]$$$.

You are given a permutation $$$p$$$ of length $$$n$$$. Your task is to find a different permutation $$$p'$$$ with the same fingerprint. Two permutations $$$p$$$ and $$$p'$$$ are considered different if there is some index $$$i$$$ such that $$$p_i \ne p'_i$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 668$$$). Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2\le n\le 100$$$)  — the length of the permutation.

The second line of each test case contains $$$n$$$ integers $$$p_1,\ldots,p_n$$$ ($$$1\le p_i\le n$$$). It is guaranteed that $$$p$$$ is a permutation.

## Output Format
For each test case, output $$$n$$$ integers $$$p'_1,\ldots, p'_n$$$ — a permutation such that $$$p'\ne p$$$ and $$$F(p')=F(p)$$$.

We can prove that for every permutation satisfying the input constraints, a solution exists.

If there are multiple solutions, you may output any.

## Examples
```input
3
2
1 2
6
2 1 6 5 4 3
5
2 4 3 1 5
```
```output
2 1
1 2 5 6 3 4
3 1 5 2 4
```

## Note
In the first test case, $$$F(p)=\mathrm{sort}([1+2])=[3]$$$.

And $$$F(p')=\mathrm{sort}([2+1])=[3]$$$.

In the second test case, $$$F(p)=\mathrm{sort}([2+1,1+6,6+5,5+4,4+3])=\mathrm{sort}([3,7,11,9,7])=[3,7,7,9,11]$$$.

And $$$F(p')=\mathrm{sort}([1+2,2+5,5+6,6+3,3+4])=\mathrm{sort}([3,7,11,9,7])=[3,7,7,9,11]$$$.

In the third test case, $$$F(p)=\mathrm{sort}([2+4,4+3,3+1,1+5])=\mathrm{sort}([6,7,4,6])=[4,6,6,7]$$$.

And $$$F(p')=\mathrm{sort}([3+1,1+5,5+2,2+4])=\mathrm{sort}([4,6,7,6])=[4,6,6,7]$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You're given an array $$$a$$$ of $$$n$$$ integers, such that $$$a_1 + a_2 + \cdots + a_n = 0$$$.

In one operation, you can choose two different indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$), decrement $$$a_i$$$ by one and increment $$$a_j$$$ by one. If $$$i < j$$$ this operation is free, otherwise it costs one coin.

How many coins do you have to spend in order to make all elements equal to $$$0$$$?

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 5000$$$). Description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$)  — the number of elements.

The next line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$). It is given that $$$\sum_{i=1}^n a_i = 0$$$.

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

## Output Format
For each test case, print the minimum number of coins we have to spend in order to make all elements equal to $$$0$$$.

## Examples
```input
7
4
-3 5 -3 1
2
1 -1
4
-3 2 -3 4
4
-1 1 1 -1
7
-5 7 -6 -4 17 -13 4
6
-1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000
1
0
```
```output
3
0
4
1
8
3000000000
0
```

## Note
Possible strategy for the first test case:

- Do $$$(i=2, j=3)$$$ three times (free), $$$a = [-3, 2, 0, 1]$$$.
- Do $$$(i=2, j=1)$$$ two times (pay two coins), $$$a = [-1, 0, 0, 1]$$$.
- Do $$$(i=4, j=1)$$$ one time (pay one coin), $$$a = [0, 0, 0, 0]$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Jett is tired after destroying the town and she wants to have a rest. She likes high places, that's why for having a rest she wants to get high and she decided to craft staircases.

A staircase is a squared figure that consists of square cells. Each staircase consists of an arbitrary number of stairs. If a staircase has $$$n$$$ stairs, then it is made of $$$n$$$ columns, the first column is $$$1$$$ cell high, the second column is $$$2$$$ cells high, $$$\ldots$$$, the $$$n$$$-th column if $$$n$$$ cells high. The lowest cells of all stairs must be in the same row.

A staircase with $$$n$$$ stairs is called nice, if it may be covered by $$$n$$$ disjoint squares made of cells. All squares should fully consist of cells of a staircase.

This is how a nice covered staircase with $$$7$$$ stairs looks like:

Find out the maximal number of different nice staircases, that can be built, using no more than $$$x$$$ cells, in total. No cell can be used more than once.

## Input Format
The first line contains a single integer $$$t$$$ $$$(1 \le t \le 1000)$$$  — the number of test cases.

The description of each test case contains a single integer $$$x$$$ $$$(1 \le x \le 10^{18})$$$  — the number of cells for building staircases.

## Output Format
For each test case output a single integer  — the number of different nice staircases, that can be built, using not more than $$$x$$$ cells, in total.

## Examples
```input
4
1
8
6
1000000000000000000
```
```output
1
2
1
30
```

## Note
In the first test case, it is possible to build only one staircase, that consists of $$$1$$$ stair. It's nice. That's why the answer is $$$1$$$.

In the second test case, it is possible to build two different nice staircases: one consists of $$$1$$$ stair, and another consists of $$$3$$$ stairs. This will cost $$$7$$$ cells. In this case, there is one cell left, but it is not possible to use it for building any nice staircases, that have not been built yet. That's why the answer is $$$2$$$.

In the third test case, it is possible to build only one of two nice staircases: with $$$1$$$ stair or with $$$3$$$ stairs. In the first case, there will be $$$5$$$ cells left, that may be used only to build a staircase with $$$2$$$ stairs. This staircase is not nice, and Jett only builds nice staircases. That's why in this case the answer is $$$1$$$. If Jett builds a staircase with $$$3$$$ stairs, then there are no more cells left, so the answer is $$$1$$$ again.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
This is the easy version of the problem. The difference between the versions is that in the easy version all prices $$$a_i$$$ are different. You can make hacks if and only if you solved both versions of the problem.

Today is Sage's birthday, and she will go shopping to buy ice spheres. All $$$n$$$ ice spheres are placed in a row and they are numbered from $$$1$$$ to $$$n$$$ from left to right. Each ice sphere has a positive integer price. In this version all prices are different.

An ice sphere is cheap if it costs strictly less than two neighboring ice spheres: the nearest to the left and the nearest to the right. The leftmost and the rightmost ice spheres are not cheap. Sage will choose all cheap ice spheres and then buy only them.

You can visit the shop before Sage and reorder the ice spheres as you wish. Find out the maximum number of ice spheres that Sage can buy, and show how the ice spheres should be reordered.

## Input Format
The first line contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the number of ice spheres in the shop.

The second line contains $$$n$$$ different integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — the prices of ice spheres.

## Output Format
In the first line print the maximum number of ice spheres that Sage can buy.

In the second line print the prices of ice spheres in the optimal order. If there are several correct answers, you can print any of them.

## Examples
```input
5
1 2 3 4 5
```
```output
2
3 1 4 2 5
```

## Note
In the example it's not possible to place ice spheres in any order so that Sage would buy $$$3$$$ of them. If the ice spheres are placed like this $$$(3, 1, 4, 2, 5)$$$, then Sage will buy two spheres: one for $$$1$$$ and one for $$$2$$$, because they are cheap.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
This is the hard version of the problem. The difference between the versions is that in the easy version all prices $$$a_i$$$ are different. You can make hacks if and only if you solved both versions of the problem.

Today is Sage's birthday, and she will go shopping to buy ice spheres. All $$$n$$$ ice spheres are placed in a row and they are numbered from $$$1$$$ to $$$n$$$ from left to right. Each ice sphere has a positive integer price. In this version, some prices can be equal.

An ice sphere is cheap if it costs strictly less than two neighboring ice spheres: the nearest to the left and the nearest to the right. The leftmost and the rightmost ice spheres are not cheap. Sage will choose all cheap ice spheres and then buy only them.

You can visit the shop before Sage and reorder the ice spheres as you wish. Find out the maximum number of ice spheres that Sage can buy, and show how the ice spheres should be reordered.

## Input Format
The first line contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the number of ice spheres in the shop.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — the prices of ice spheres.

## Output Format
In the first line print the maximum number of ice spheres that Sage can buy.

In the second line print the prices of ice spheres in the optimal order. If there are several correct answers, you can print any of them.

## Examples
```input
7
1 3 2 2 4 5 4
```
```output
3
3 1 4 2 4 2 5
```

## Note
In the sample it's not possible to place the ice spheres in any order so that Sage would buy $$$4$$$ of them. If the spheres are placed in the order $$$(3, 1, 4, 2, 4, 2, 5)$$$, then Sage will buy one sphere for $$$1$$$ and two spheres for $$$2$$$ each.

Now solve the problem and return the code.