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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a binary$$$^\dagger$$$ pattern $$$p$$$ of length $$$n$$$.

A binary string $$$q$$$ of the same length $$$n$$$ is called good if for every $$$i$$$ ($$$1 \leq i \leq n$$$), there exist indices $$$l$$$ and $$$r$$$ such that:

- $$$1 \leq l \leq i \leq r \leq n$$$, and
- $$$p_i$$$ is a mode$$$^\ddagger$$$ of the string $$$q_lq_{l+1}\ldots q_r$$$.

Count the number of good binary strings modulo $$$998\,244\,353$$$.

$$$^\dagger$$$ A binary string is a string that only consists of characters $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$.

$$$^\ddagger$$$ Character $$$c$$$ is a mode of string $$$t$$$ of length $$$m$$$ if the number of occurrences of $$$c$$$ in $$$t$$$ is at least $$$\lceil \frac{m}{2} \rceil$$$. For example, $$$\mathtt{0}$$$ is a mode of $$$\mathtt{010}$$$, $$$\mathtt{1}$$$ is not a mode of $$$\mathtt{010}$$$, and both $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$ are modes of $$$\mathtt{011010}$$$.

## Input Format
The first line of input contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the binary string $$$p$$$.

The second line of input contains a binary string $$$p$$$ of length $$$n$$$ consisting of characters 0 and 1.

## Output Format
Output the number of good strings modulo $$$998\,244\,353$$$.

## Examples
```input
1
0
```
```output
1
```
-----
```input
3
111
```
```output
5
```
-----
```input
4
1011
```
```output
9
```
-----
```input
6
110001
```
```output
36
```
-----
```input
12
111010001111
```
```output
2441
```

## Note
In the second example, the good strings are

- $$$\mathtt{010}$$$;
- $$$\mathtt{011}$$$;
- $$$\mathtt{101}$$$;
- $$$\mathtt{110}$$$;
- $$$\mathtt{111}$$$.

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
Let's call an array $$$a$$$ sorted if $$$a_1 \leq a_2 \leq \ldots \leq a_{n - 1} \leq a_{n}$$$.

You are given two of Farmer John's favorite integers, $$$n$$$ and $$$k$$$. He challenges you to find any array $$$a_1, a_2, \ldots, a_{n}$$$ satisfying the following requirements:

- $$$1 \leq a_i \leq 10^9$$$ for each $$$1 \leq i \leq n$$$;
- Out of the $$$n$$$ total cyclic shifts of $$$a$$$, exactly $$$k$$$ of them are sorted.$$$^\dagger$$$

If there is no such array $$$a$$$, output $$$-1$$$.

$$$^\dagger$$$The $$$x$$$-th ($$$1 \leq x \leq n$$$) cyclic shift of the array $$$a$$$ is $$$a_x, a_{x+1} \ldots a_n, a_1, a_2 \ldots a_{x - 1}$$$. If $$$c_{x, i}$$$ denotes the $$$i$$$'th element of the $$$x$$$'th cyclic shift of $$$a$$$, exactly $$$k$$$ such $$$x$$$ should satisfy $$$c_{x,1} \leq c_{x,2} \leq \ldots \leq c_{x, n - 1} \leq c_{x, n}$$$.

For example, the cyclic shifts for $$$a = [1, 2, 3, 3]$$$ are the following:

- $$$x = 1$$$: $$$[1, 2, 3, 3]$$$ (sorted);
- $$$x = 2$$$: $$$[2, 3, 3, 1]$$$ (not sorted);
- $$$x = 3$$$: $$$[3, 3, 1, 2]$$$ (not sorted);
- $$$x = 4$$$: $$$[3, 1, 2, 3]$$$ (not sorted).

## Input Format
The first line contains $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of test cases.

Each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 10^3$$$) — the length of $$$a$$$ and the number of sorted cyclic shifts $$$a$$$ must have.

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

## Output Format
For each test case, print a single line:

- if there is a valid array $$$a$$$, output $$$n$$$ integers, representing $$$a_1, a_2, \ldots, a_{n}$$$;
- otherwise, output $$$-1$$$.

If there are multiple solutions, print any of them.

## Examples
```input
3
2 2
3 1
3 2
```
```output
1 1
69420 69 420
-1
```

## Note
In the first testcase, $$$a = [1, 1]$$$ satisfies $$$n = 2, k = 2$$$:

The two cyclic shifts of $$$a$$$ are $$$[a_1, a_2]$$$ and $$$[a_2, a_1]$$$, which are both $$$[1, 1]$$$ and are sorted.

In the second testcase, $$$a = [69\,420, 69, 420]$$$ satisfies $$$n = 3, k = 1$$$:

The three cyclic shifts of $$$a$$$ are $$$[a_1, a_2, a_3]$$$, $$$[a_2, a_3, a_1]$$$, $$$[a_3, a_1, a_2]$$$, which are $$$[69\,420, 69, 420]$$$, $$$[69, 420, 69\,420]$$$, and $$$[420, 69\,420, 69]$$$, respectively.

Only $$$[69, 420, 69\,420]$$$ is sorted.

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.5 seconds
Memory limit: 256.0 MB

# Problem
Farmer John has a permutation $$$p_1, p_2, \ldots, p_n$$$, where every integer from $$$0$$$ to $$$n-1$$$ occurs exactly once. He gives Bessie an array $$$a$$$ of length $$$n$$$ and challenges her to construct $$$p$$$ based on $$$a$$$.

The array $$$a$$$ is constructed so that $$$a_i$$$ = $$$\texttt{MEX}(p_1, p_2, \ldots, p_i) - p_i$$$, where the $$$\texttt{MEX}$$$ of an array is the minimum non-negative integer that does not appear in that array. For example, $$$\texttt{MEX}(1, 2, 3) = 0$$$ and $$$\texttt{MEX}(3, 1, 0) = 2$$$.

Help Bessie construct any valid permutation $$$p$$$ that satisfies $$$a$$$. The input is given in such a way that at least one valid $$$p$$$ exists. If there are multiple possible $$$p$$$, it is enough to print one of them.

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the lengths of $$$p$$$ and $$$a$$$.

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

It is guaranteed that there is at least one valid $$$p$$$ for the given data.

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 $$$n$$$ integers on a new line, the elements of $$$p$$$.

If there are multiple solutions, print any of them.

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

## Note
In the first case, $$$p = [0, 1, 4, 2, 3]$$$ is one possible output.

$$$a$$$ will then be calculated as $$$a_1 = \texttt{MEX}(0) - 0 = 1$$$, $$$a_2 = \texttt{MEX}(0, 1) - 1 = 1$$$, $$$a_3 = \texttt{MEX}(0, 1, 4) - 4 = -2$$$, $$$a_4 = \texttt{MEX}(0, 1, 4, 2) - 2 = 1$$$, $$$a_5 = \texttt{MEX}(0, 1, 4, 2, 3) - 3 = 2$$$.

So, as required, $$$a$$$ will be $$$[1, 1, -2, 1, 2]$$$.

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
This is the easy version of the problem. The only difference between the two versions is the constraint on $$$y$$$. In this version $$$y = 0$$$. You can make hacks only if both versions are solved.

Bessie has received a birthday cake from her best friend Elsie, and it came in the form of a regular polygon with $$$n$$$ sides. The vertices of the cake are numbered from $$$1$$$ to $$$n$$$ clockwise. You and Bessie are going to choose some of those vertices to cut non-intersecting diagonals into the cake. In other words, the endpoints of the diagonals must be part of the chosen vertices.

Bessie would only like to give out pieces of cake which result in a triangle to keep consistency. The size of the pieces doesn't matter, and the whole cake does not have to be separated into all triangles (other shapes are allowed in the cake, but those will not be counted).

Bessie has already chosen $$$x$$$ of those vertices that can be used to form diagonals. She wants you to choose no more than $$$y$$$ other vertices such that the number of triangular pieces of cake she can give out is maximized.

What is the maximum number of triangular pieces of cake Bessie can give out?

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

The first line of each test case consists of three integers, $$$n$$$, $$$x$$$, and $$$y$$$ ($$$4 \leq n \leq 10^9$$$, $$$2 \leq x \leq \min(n, 2 \cdot 10^5)$$$, $$$y = 0$$$) — the number of sides of the polygon, number of vertices Bessie has chosen, and the maximum number of other vertices you can choose.

The second line consists of $$$x$$$ distinct integers from $$$1$$$ to $$$n$$$, representing the vertices Bessie has chosen.

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

## Output Format
For each test case, output a single integer: the maximum number of non-intersecting triangular pieces of cake she can give out.

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

## Note
In test cases $$$1$$$, $$$2$$$ and $$$3$$$, you can get $$$2$$$, $$$6$$$ and $$$2$$$ non-intersecting triangular pieces of cake, respectively. A possible construction is shown in the following pictures:

The green dots represent vertices that can be used, the blue lines represent diagonals that are drawn, and the red numbers represent triangles that are counted.

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
This is the hard version of the problem. The only difference between the two versions is the constraint on $$$y$$$. In this version $$$0 \leq y \leq n - x$$$. You can make hacks only if both versions are solved.

Bessie has received a birthday cake from her best friend Elsie, and it came in the form of a regular polygon with $$$n$$$ sides. The vertices of the cake are numbered from $$$1$$$ to $$$n$$$ clockwise. You and Bessie are going to choose some of those vertices to cut non-intersecting diagonals into the cake. In other words, the endpoints of the diagonals must be part of the chosen vertices.

Bessie would only like to give out pieces of cake which result in a triangle to keep consistency. The size of the pieces doesn't matter, and the whole cake does not have to be separated into all triangles (other shapes are allowed in the cake, but those will not be counted).

Bessie has already chosen $$$x$$$ of those vertices that can be used to form diagonals. She wants you to choose no more than $$$y$$$ other vertices such that the number of triangular pieces of cake she can give out is maximized.

What is the maximum number of triangular pieces of cake Bessie can give out?

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

The first line of each test case consists of three integers, $$$n$$$, $$$x$$$, and $$$y$$$ ($$$4 \leq n \leq 10^9$$$, $$$2 \leq x \leq \min(n, 2 \cdot 10^5)$$$, $$$0 \leq y \leq n - x$$$) — the number of sides of the polygon, number of vertices Bessie has chosen, and the maximum number of other vertices you can choose.

The second line consists of $$$x$$$ distinct integers from $$$1$$$ to $$$n$$$, representing the vertices Bessie has chosen.

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

## Output Format
For each test case, output a single integer: the maximum number of non-intersecting triangular pieces of cake she can give out.

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

## Note
In test cases $$$1$$$, $$$2$$$ and $$$3$$$, you can get $$$6$$$, $$$5$$$ and $$$2$$$ non-intersecting triangular pieces of cake, respectively. A possible construction is shown in the following pictures:

The green dots represent vertices that Bessie chose, the yellow dots represent vertices that you chose, the blue lines represent diagonals that are drawn, and the red numbers represent triangles that are counted.

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: 4.5 seconds
Memory limit: 512.0 MB

# Problem
Elsie is learning how to paint. She has a canvas of $$$n$$$ cells numbered from $$$1$$$ to $$$n$$$ and can paint any (potentially empty) subset of cells.

Elsie has a 2D array $$$a$$$ which she will use to evaluate paintings. Let the maximal contiguous intervals of painted cells in a painting be $$$[l_1,r_1],[l_2,r_2],\ldots,[l_x,r_x]$$$. The beauty of the painting is the sum of $$$a_{l_i,r_i}$$$ over all $$$1 \le i \le x$$$. In the image above, the maximal contiguous intervals of painted cells are $$$[2,4],[6,6],[8,9]$$$ and the beauty of the painting is $$$a_{2,4}+a_{6,6}+a_{8,9}$$$.

There are $$$2^n$$$ ways to paint the strip. Help Elsie find the $$$k$$$ largest possible values of the beauty of a painting she can obtain, among all these ways. Note that these $$$k$$$ values do not necessarily have to be distinct. It is guaranteed that there are at least $$$k$$$ different ways to paint the canvas.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of test cases.

The first line of each test case contains $$$2$$$ integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^3$$$, $$$1 \leq k \leq \min(2^n, 5 \cdot 10^3)$$$) — the number of cells and the number of largest values of the beauty of a painting you must find.

The next $$$n$$$ lines of each test case describe $$$a$$$ where the $$$i$$$-th of which contains $$$n-i+1$$$ integers $$$a_{i,i},a_{i,i+1},\ldots,a_{i,n}$$$ ($$$-10^6 \leq a_{i,j} \leq 10^6$$$).

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

## Output Format
For each test case, output $$$k$$$ integers in one line: the $$$i$$$-th of them must represent the $$$i$$$-th largest value of the beauty of a painting Elsie can obtain.

## Examples
```input
4
1 2
-5
2 4
2 -3
-1
3 8
2 4 3
1 3
5
6 20
0 -6 -3 0 -6 -2
-7 -5 -2 -3 -4
7 0 -9 -4
2 -1 1
1 -2
-6
```
```output
0 -5 
2 0 -1 -3 
7 5 4 3 3 2 1 0 
8 8 7 7 5 5 2 2 1 1 1 1 1 1 0 0 0 0 0 -1
```

## Note
In the first test case, Elsie can either paint the only cell or not paint it. If she paints the only cell, the beauty of the painting is $$$-5$$$. If she chooses not to paint it, the beauty of the painting is $$$0$$$. Thus, the largest beauty she can obtain is $$$0$$$ and the second largest beauty she can obtain is $$$-5$$$.

Below is an illustration of the third test case.

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
Yarik's birthday is coming soon, and Mark decided to give him an array $$$a$$$ of length $$$n$$$.

Mark knows that Yarik loves bitwise operations very much, and he also has a favorite number $$$x$$$, so Mark wants to find the maximum number $$$k$$$ such that it is possible to select pairs of numbers [$$$l_1, r_1$$$], [$$$l_2, r_2$$$], $$$\ldots$$$ [$$$l_k, r_k$$$], such that:

- $$$l_1 = 1$$$.
- $$$r_k = n$$$.
- $$$l_i \le r_i$$$ for all $$$i$$$ from $$$1$$$ to $$$k$$$.
- $$$r_i + 1 = l_{i + 1}$$$ for all $$$i$$$ from $$$1$$$ to $$$k - 1$$$.
- $$$(a_{l_1} \oplus a_{l_1 + 1} \oplus \ldots \oplus a_{r_1}) | (a_{l_2} \oplus a_{l_2 + 1} \oplus \ldots \oplus a_{r_2}) | \ldots | (a_{l_k} \oplus a_{l_k + 1} \oplus \ldots \oplus a_{r_k}) \le x$$$, where $$$\oplus$$$ denotes the operation of bitwise XOR, and $$$|$$$ denotes the operation of bitwise OR.

If such $$$k$$$ does not exist, then output $$$-1$$$.

## Input Format
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The following lines contain the descriptions of the test cases.

The first line of each test case contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 10^5, 0 \le x < 2^{30}$$$) — the length of the array $$$a$$$ and the number $$$x$$$ respectively.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^{30}$$$) — the array $$$a$$$ itself.

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

## Output Format
For each test case, output a single integer on a separate line — the maximum suitable number $$$k$$$, and $$$-1$$$ if such $$$k$$$ does not exist.

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

## Note
In the first test case, you can take $$$k$$$ equal to $$$2$$$ and choose two segments [$$$1, 1$$$] and [$$$2, 3$$$], $$$(1) | (2 \oplus 3) = 1$$$. It can be shown that $$$2$$$ is the maximum possible answer.

In the second test case, the segments [$$$1, 1$$$] and [$$$2, 2$$$] are suitable, $$$(1) | (1) = 1$$$. It is not possible to make more segments.

In the third test case, it is not possible to choose $$$2$$$ segments, as $$$(1) | (3) = 3 > 2$$$, so the optimal answer is $$$1$$$.

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
Some permutation of length $$$n$$$ is guessed.

You are given the indices of its prefix maximums and suffix maximums.

Recall that a permutation of length $$$k$$$ is an array of size $$$k$$$ such that each integer from $$$1$$$ to $$$k$$$ occurs exactly once.

Prefix maximums are the elements that are the maximum on the prefix ending at that element. More formally, the element $$$a_i$$$ is a prefix maximum if $$$a_i > a_j$$$ for every $$$j < i$$$.

Similarly, suffix maximums are defined, the element $$$a_i$$$ is a suffix maximum if $$$a_i > a_j$$$ for every $$$j > i$$$.

You need to output the number of different permutations that could have been guessed.

As this number can be very large, output the answer modulo $$$10^9 + 7$$$.

## Input Format
Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains three integers $$$n, m_1$$$ and $$$m_2$$$ ($$$1 \le m_1, m_2 \le n \le 2 \cdot 10^5$$$) — the length of the permutation, the number of prefix maximums, and the number of suffix maximums, respectively.

The second line of each test case contains $$$m_1$$$ integers $$$p_1 < p_2 < \ldots < p_{m_1}$$$ ($$$1 \le p_i \le n$$$) — the indices of the prefix maximums in increasing order.

The third line of each test case contains $$$m_2$$$ integers $$$s_1 < s_2 < \ldots < s_{m_2}$$$ ($$$1 \le s_i \le n$$$) — the indices of the suffix maximums in increasing order.

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

## Output Format
For each test case, output a single integer on a separate line — the number of suitable permutations modulo $$$10^9 + 7$$$.

## Examples
```input
6
1 1 1
1
1
4 2 3
1 2
2 3 4
3 3 1
1 2 3
3
5 3 4
1 2 3
2 3 4 5
20 5 4
1 2 3 4 12
12 13 18 20
6 2 3
1 3
3 4 6
```
```output
1
3
1
0
317580808
10
```

## Note
The following permutations are suitable for the second set of input data:

- $$$[1, 4, 3, 2]$$$
- $$$[2, 4, 3, 1]$$$
- $$$[3, 4, 2, 1]$$$

The following permutations are suitable for the sixth set of input data:

- $$$[2, 1, 6, 5, 3, 4]$$$
- $$$[3, 1, 6, 5, 2, 4]$$$
- $$$[3, 2, 6, 5, 1, 4]$$$
- $$$[4, 1, 6, 5, 2, 3]$$$
- $$$[4, 2, 6, 5, 1, 3]$$$
- $$$[4, 3, 6, 5, 1, 2]$$$
- $$$[5, 1, 6, 4, 2, 3]$$$
- $$$[5, 2, 6, 4, 1, 3]$$$
- $$$[5, 3, 6, 4, 1, 2]$$$
- $$$[5, 4, 6, 3, 1, 2]$$$

Now solve the problem and return the code.