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: 4.0 seconds
Memory limit: 64.0 MB

# Problem
This is the easy version of the problem. The only difference between the versions is the constraints on $$$n$$$, $$$k$$$, $$$a_i$$$, and the sum of $$$n$$$ over all test cases. You can make hacks only if both versions of the problem are solved.

Note the unusual memory limit.

You are given an array of integers $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$, and an integer $$$k$$$.

The cost of an array of integers $$$p_1, p_2, \ldots, p_n$$$ of length $$$n$$$ is $$$$$$\max\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right) - \min\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right).$$$$$$

Here, $$$\lfloor \frac{x}{y} \rfloor$$$ denotes the integer part of the division of $$$x$$$ by $$$y$$$. Find the minimum cost of an array $$$p$$$ such that $$$1 \le p_i \le k$$$ for all $$$1 \le i \le n$$$.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 3000$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \ldots \le a_n \le 3000$$$).

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

## Output Format
For each test case, print a single integer — the minimum possible cost of an array $$$p$$$ satisfying the condition above.

## Examples
```input
7
5 2
4 5 6 8 11
5 12
4 5 6 8 11
3 1
2 9 15
7 3
2 3 5 5 6 9 10
6 56
54 286 527 1436 2450 2681
3 95
16 340 2241
2 2
1 3
```
```output
2
0
13
1
4
7
0
```

## Note
In the first test case, the optimal array is $$$p = [1, 1, 1, 2, 2]$$$. The resulting array of values of $$$\lfloor \frac{a_i}{p_i} \rfloor$$$ is $$$[4, 5, 6, 4, 5]$$$. The cost of $$$p$$$ is $$$\max\limits_{1 \le i \le n}(\lfloor \frac{a_i}{p_i} \rfloor) - \min\limits_{1 \le i \le n}(\lfloor \frac{a_i}{p_i} \rfloor) = 6 - 4 = 2$$$. We can show that there is no array (satisfying the condition from the statement) with a smaller cost.

In the second test case, one of the optimal arrays is $$$p = [12, 12, 12, 12, 12]$$$, which results in all $$$\lfloor \frac{a_i}{p_i} \rfloor$$$ being $$$0$$$.

In the third test case, the only possible array is $$$p = [1, 1, 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
How to make a cake you'll never eat.

Ingredients.

- 2 carrots
- 0 calories
- 100 g chocolate spread
- 1 pack of flour
- 1 egg

Method.

1. Put calories into the mixing bowl.
2. Take carrots from refrigerator.
3. Chop carrots.
4. Take chocolate spread from refrigerator.
5. Put chocolate spread into the mixing bowl.
6. Combine pack of flour into the mixing bowl.
7. Fold chocolate spread into the mixing bowl.
8. Add chocolate spread into the mixing bowl.
9. Put pack of flour into the mixing bowl.
10. Add egg into the mixing bowl.
11. Fold pack of flour into the mixing bowl.
12. Chop carrots until choped.
13. Pour contents of the mixing bowl into the baking dish.

Serves 1.

## Input Format
The only line of input contains a sequence of integers a0, a1, ... (1 ≤ a0 ≤ 100, 0 ≤ ai ≤ 1000 for i ≥ 1).

## Output Format
Output a single integer.

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

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: 64.0 MB

# Problem
qd ucyhf yi q fhycu dkcruh mxeiu huluhiu yi q tyvvuhudj fhycu dkcruh. oekh jqia yi je vydt jxu djx ucyhf.

## Input Format
jxu ydfkj sediyiji ev q iydwbu ydjuwuh d (1 ≤ d ≤ 11184) — jxu edu-rqiut ydtun ev jxu ucyhf je vydt.

## Output Format
ekjfkj q iydwbu dkcruh.

## Examples
```input
1
```
```output
13
```

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
While working at DTL, Ela is very aware of her physical and mental health. She started to practice various sports, such as Archery, Yoga, and Football.

Since she started engaging in sports activities, Ela switches to trying a new sport on days she considers being "Luxury" days. She counts the days since she started these activities, in which the day she starts is numbered as day $$$1$$$. A "Luxury" day is the day in which the number of this day is a luxurious number.

An integer $$$x$$$ is called a luxurious number if it is divisible by $$${\lfloor \sqrt{x} \rfloor}$$$.

Here $$$\lfloor r \rfloor$$$ denotes the "floor" of a real number $$$r$$$. In other words, it's the largest integer not greater than $$$r$$$.

For example: $$$8$$$, $$$56$$$, $$$100$$$ are luxurious numbers, since $$$8$$$ is divisible by $$$\lfloor \sqrt{8} \rfloor = \lfloor 2.8284 \rfloor = 2$$$, $$$56$$$ is divisible $$$\lfloor \sqrt{56} \rfloor = \lfloor 7.4833 \rfloor = 7$$$, and $$$100$$$ is divisible by $$$\lfloor \sqrt{100} \rfloor = \lfloor 10 \rfloor = 10$$$, respectively. On the other hand $$$5$$$, $$$40$$$ are not, since $$$5$$$ are not divisible by $$$\lfloor \sqrt{5} \rfloor = \lfloor 2.2361 \rfloor = 2$$$, and $$$40$$$ are not divisible by $$$\lfloor \sqrt{40} \rfloor = \lfloor 6.3246 \rfloor = 6$$$.

Being a friend of Ela, you want to engage in these fitness activities with her to keep her and yourself accompanied (and have fun together, of course). Between day $$$l$$$ and day $$$r$$$, you want to know how many times she changes the activities.

## Input Format
Each test contains multiple test cases. The first line has the number of test cases $$$t$$$ ($$$1 \le t \le 10\ 000$$$). The description of the test cases follows.

The only line of each test case contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 10^{18}$$$) — the intervals at which you want to know how many times Ela changes her sports.

## Output Format
For each test case, output an integer that denotes the answer.

## Examples
```input
5
8 19
8 20
119 121
1 100000000000000000
1234567891011 1000000000000000000
```
```output
5
6
2
948683296
2996666667
```

## Note
In the first test case, $$$5$$$ luxury numbers in range $$$[8, 19]$$$ are: $$$8, 9, 12, 15, 16$$$.

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
Ela likes Chess a lot. During breaks, she usually challenges her co-worker in DTL to some chess games. She's not an expert at classic chess, but she's very interested in Chess variants, where she has to adapt to new rules and test her tactical mindset to win the game.

The problem, which involves a non-standard chess pieces type that is described below, reads: given $$$3$$$ white crickets on a $$$n \cdot n$$$ board, arranged in an "L" shape next to each other, there are no other pieces on the board. Ela wants to know with a finite number of moves, can she put any white cricket on the square on row $$$x$$$, column $$$y$$$?

An "L"-shape piece arrangement can only be one of the below:

For simplicity, we describe the rules for crickets on the board where only three white crickets are. It can move horizontally, vertically, or diagonally, but only to a square in some direction that is immediately after another cricket piece (so that it must jump over it). If the square immediately behind the piece is unoccupied, the cricket will occupy the square. Otherwise (when the square is occupied by another cricket, or does not exist), the cricket isn't allowed to make such a move.

See an example of valid crickets' moves on the pictures in the Note section.

## 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 $$$n$$$ ($$$4 \le n \le 10^5$$$) — denotes the size of the chessboard.

The second line of each test case contains 6 numbers: $$$r_1$$$, $$$c_1$$$, $$$r_2$$$, $$$c_2$$$, $$$r_3$$$, $$$c_3$$$ ($$$1 \le r_1, c_1, r_2, c_2, r_3, c_3 \le n$$$) — coordinates of the crickets. The input ensures that the three crickets are arranged in an "L" shape that the legend stated.

The third line of each test case contains 2 numbers: $$$x$$$, $$$y$$$ ($$$1 \le x, y \le n$$$) — coordinates of the target square.

## Output Format
For each test case, print "YES" or "NO" to denotes whether Ela can put a cricket on the target square.

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

## Note
Here's the solution for the first test case. The red square denotes where the crickets need to reach. Note that in chess horizontals are counted from bottom to top, as well as on this picture.

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 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.

For a given number $$$n$$$ you need to make a permutation $$$p$$$ such that two requirements are satisfied at the same time:

- For each element $$$p_i$$$, at least one of its neighbors has a value that differs from the value of $$$p_i$$$ by one. That is, for each element $$$p_i$$$ ($$$1 \le i \le n$$$), at least one of its neighboring elements (standing to the left or right of $$$p_i$$$) must be $$$p_i + 1$$$, or $$$p_i - 1$$$.
- the permutation must have no fixed points. That is, for every $$$i$$$ ($$$1 \le i \le n$$$), $$$p_i \neq i$$$ must be satisfied.

Let's call the permutation that satisfies these requirements funny.

For example, let $$$n = 4$$$. Then [$$$4, 3, 1, 2$$$] is a funny permutation, since:

- to the right of $$$p_1=4$$$ is $$$p_2=p_1-1=4-1=3$$$;
- to the left of $$$p_2=3$$$ is $$$p_1=p_2+1=3+1=4$$$;
- to the right of $$$p_3=1$$$ is $$$p_4=p_3+1=1+1=2$$$;
- to the left of $$$p_4=2$$$ is $$$p_3=p_4-1=2-1=1$$$.
- for all $$$i$$$ is $$$p_i \ne i$$$.

For a given positive integer $$$n$$$, output any funny permutation of length $$$n$$$, or output -1 if funny permutation of length $$$n$$$ does not exist.

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

The description of the test cases follows.

Each test case consists of f single line containing one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

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, print on a separate line:

- any funny permutation $$$p$$$ of length $$$n$$$;
- or the number -1 if the permutation you are looking for does not exist.

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

## Note
The first test case is explained in the problem statement.

In the second test case, it is not possible to make the required permutation: permutations $$$[1, 2, 3]$$$, $$$[1, 3, 2]$$$, $$$[2, 1, 3]$$$, $$$[3, 2, 1]$$$ have fixed points, and in $$$[2, 3, 1]$$$ and $$$[3, 1, 2]$$$ the first condition is met not for all positions.

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
The girl named Masha was walking in the forest and found a complete binary tree of height $$$n$$$ and a permutation $$$p$$$ of length $$$m=2^n$$$.

A complete binary tree of height $$$n$$$ is a rooted tree such that every vertex except the leaves has exactly two sons, and the length of the path from the root to any of the leaves is $$$n$$$. The picture below shows the complete binary tree for $$$n=2$$$.

A permutation is an array consisting of $$$n$$$ different integers from $$$1$$$ to $$$n$$$. For example, [$$$2,3,1,5,4$$$] is a permutation, but [$$$1,2,2$$$] is not ($$$2$$$ occurs twice), and [$$$1,3,4$$$] is also not a permutation ($$$n=3$$$, but there is $$$4$$$ in the array).

Let's enumerate $$$m$$$ leaves of this tree from left to right. The leaf with the number $$$i$$$ contains the value $$$p_i$$$ ($$$1 \le i \le m$$$).

For example, if $$$n = 2$$$, $$$p = [3, 1, 4, 2]$$$, the tree will look like this:

Masha considers a tree beautiful if the values in its leaves are ordered from left to right in increasing order.

In one operation, Masha can choose any non-leaf vertex of the tree and swap its left and right sons (along with their subtrees).

For example, if Masha applies this operation to the root of the tree discussed above, it will take the following form:

Help Masha understand if she can make a tree beautiful in a certain number of operations. If she can, then output the minimum number of operations to make the tree beautiful.

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

In each test case, the first line contains an integer $$$m$$$ ($$$1 \le m \le 262144$$$), which is a power of two  — the size of the permutation $$$p$$$.

The second line contains $$$m$$$ integers: $$$p_1, p_2, \dots, p_m$$$ ($$$1 \le p_i \le m$$$) — the permutation $$$p$$$.

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

## Output Format
For each test case in a separate line, print the minimum possible number of operations for which Masha will be able to make the tree beautiful or -1, if this is not possible.

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

## Note
Consider the first test.

In the first test case, you can act like this (the vertex to which the operation is applied at the current step is highlighted in purple):

In the second test case, it can be shown that it is impossible to make a tree beautiful.

In the third test case, the tree is already beautiful.

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
Doremy has $$$n$$$ buckets of paint which is represented by an array $$$a$$$ of length $$$n$$$. Bucket $$$i$$$ contains paint with color $$$a_i$$$.

Let $$$c(l,r)$$$ be the number of distinct elements in the subarray $$$[a_l,a_{l+1},\ldots,a_r]$$$. Choose $$$2$$$ integers $$$l$$$ and $$$r$$$ such that $$$l \leq r$$$ and $$$r-l-c(l,r)$$$ is maximized.

## Input Format
The input 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 description of the test cases follows.

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

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$).

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

## Output Format
For each test case, output $$$l$$$ and $$$r$$$ such that $$$l \leq r$$$ and $$$r-l-c(l,r)$$$ is maximized.

If there are multiple solutions, you may output any.

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

## Note
In the first test case, $$$a=[1,3,2,2,4]$$$.

- When $$$l=1$$$ and $$$r=3$$$, $$$c(l,r)=3$$$ (there are $$$3$$$ distinct elements in $$$[1,3,2]$$$).
- When $$$l=2$$$ and $$$r=4$$$, $$$c(l,r)=2$$$ (there are $$$2$$$ distinct elements in $$$[3,2,2]$$$).

It can be shown that choosing $$$l=2$$$ and $$$r=4$$$ maximizes the value of $$$r-l-c(l,r)$$$ at $$$0$$$.

For the second test case, $$$a=[1,2,3,4,5]$$$.

- When $$$l=1$$$ and $$$r=5$$$, $$$c(l,r)=5$$$ (there are $$$5$$$ distinct elements in $$$[1,2,3,4,5]$$$).
- When $$$l=3$$$ and $$$r=3$$$, $$$c(l,r)=1$$$ (there is $$$1$$$ distinct element in $$$[3]$$$).

It can be shown that choosing $$$l=1$$$ and $$$r=5$$$ maximizes the value of $$$r-l-c(l,r)$$$ at $$$-1$$$. Choosing $$$l=3$$$ and $$$r=3$$$ is also acceptable.

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
"Everybody! Doremy's Perfect Math Class is about to start! Come and do your best if you want to have as much IQ as me!" In today's math class, Doremy is teaching everyone subtraction. Now she gives you a quiz to prove that you are paying attention in class.

You are given a set $$$S$$$ containing positive integers. You may perform the following operation some (possibly zero) number of times:

- choose two integers $$$x$$$ and $$$y$$$ from the set $$$S$$$ such that $$$x > y$$$ and $$$x - y$$$ is not in the set $$$S$$$.
- add $$$x-y$$$ into the set $$$S$$$.

You need to tell Doremy the maximum possible number of integers in $$$S$$$ if the operations are performed optimally. It can be proven that this number is finite.

## Input Format
The input 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 description of the test cases follows.

The first line contains an integer $$$n$$$ ($$$2 \le n\le 10^5$$$) — the size of the set $$$S$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$1\le a_1 < a_2 < \cdots < a_n \le 10^9$$$) — the positive integers in $$$S$$$.

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, you need to output the maximum possible number of integers in $$$S$$$. It can be proven that this value is finite.

## Examples
```input
2
2
1 2
3
5 10 25
```
```output
2
5
```

## Note
In the first test case, no such $$$x$$$ and $$$y$$$ exist. The maximum possible number of integers in $$$S$$$ is $$$2$$$.

In the second test case,

- $$$S=\{5,10,25\}$$$ at first. You can choose $$$x=25$$$, $$$y=10$$$, then add $$$x-y=15$$$ to the set.
- $$$S=\{5,10,15,25\}$$$ now. You can choose $$$x=25$$$, $$$y=5$$$, then add $$$x-y=20$$$ to the set.
- $$$S=\{5,10,15,20,25\}$$$ now. You can not perform any operation now.

After performing all operations, the number of integers in $$$S$$$ is $$$5$$$. It can be proven that no other sequence of operations allows $$$S$$$ to contain more than $$$5$$$ integers.

Now solve the problem and return the code.