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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
There is a street that can be represented as an array of length $$$n$$$.

There are two policemen patrolling a street: the first one is standing at the point $$$x$$$ of the street and the second one is standing at the point $$$y$$$ of the street.

During one minute, both policemen can decide what to do (independently): move left (if the current position is greater than $$$1$$$), move right (if the current position is less than $$$n$$$), or do nothing.

The street is considered clear if each point of the street is visited by at least one policeman.

Your task is to find the minimum number of minutes the policemen need to visit each point of the street (again, each point should be visited by at least one of them).

You have to answer $$$t$$$ independent test cases.

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

The only line of the test case contains three integers $$$n$$$, $$$x$$$ and $$$y$$$ ($$$2 \le n \le 10^6$$$; $$$1 \le x, y \le n$$$; $$$x \ne y$$$) — the length of the street, the position of the first policeman and the position of the second policeman, respectively.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$10^6$$$ ($$$\sum n \le 10^6$$$).

## Output Format
For each test case, print one integer — the minimum number of minutes the policemen need to visit each point of the street.

## Examples
```input
6
4 1 2
7 7 1
10 2 6
8 5 2
2 1 2
20 4 14
```
```output
2
3
5
4
0
12
```

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarp has decided to do a problemsolving marathon. He wants to solve $$$s$$$ problems in $$$n$$$ days. Let $$$a_i$$$ be the number of problems he solves during the $$$i$$$-th day. He wants to find a distribution of problems into days such that:

- $$$a_i$$$ is an integer value for all $$$i$$$ from $$$1$$$ to $$$n$$$;
- $$$a_i \ge 1$$$ for all $$$i$$$ from $$$1$$$ to $$$n$$$;
- $$$a_{i + 1} \ge a_i$$$ for all $$$i$$$ from $$$1$$$ to $$$n-1$$$;
- $$$a_{i + 1} \le 2 \cdot a_i$$$ for all $$$i$$$ from $$$1$$$ to $$$n-1$$$;
- $$$a_n$$$ is maximized.

Note that $$$a_1$$$ can be arbitrarily large.

What is the largest value of $$$a_n$$$ Polycarp can obtain?

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

Then the descriptions of $$$t$$$ testcases follow.

The only line of each testcase contains two integers $$$n$$$ and $$$s$$$ ($$$1 \le n \le s \le 10^{18}$$$) — the number of days and the number of problems Polycarp wants to solve.

It's guaranteed that the distribution always exists within the given constraints.

## Output Format
For each testcase print a single integer — the maximum value of $$$a_n$$$.

## Examples
```input
3
1 15
3 9
2 6
```
```output
15
4
4
```

## Note
In the first testcase there is only one distribution: $$$[15]$$$.

In the second testcase the distribution that maximizes $$$a_n$$$ is: $$$[2, 3, 4]$$$.

In the third testcase the distribution that maximizes $$$a_n$$$ is: $$$[2, 4]$$$. $$$[3, 3]$$$ is a valid distribution but $$$a_n=3$$$ which is smaller than $$$4$$$. $$$[1, 5]$$$ is not a valid distribution because $$$5 > 2 \cdot 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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
A subsequence is a sequence that can be obtained from another sequence by removing some elements without changing the order of the remaining elements.

A palindromic sequence is a sequence that is equal to the reverse of itself.

You are given a sequence of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$. Any integer value appears in $$$a$$$ no more than twice.

What is the length of the longest palindromic subsequence of sequence $$$a$$$?

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

Then the descriptions of $$$t$$$ testcases follow.

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 250\,000$$$) — the number of elements in the sequence.

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

Any integer value appears in $$$a$$$ no more than twice. The sum of $$$n$$$ over all testcases doesn't exceed $$$250\,000$$$.

## Output Format
For each testcase print a single integer — the length of the longest palindromic subsequence of sequence $$$a$$$.

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

## Note
Here are the longest palindromic subsequences for the example testcases:

- 2 1 3 1 5 2
- 1 3 3 4 4 1 or 1 3 3 4 4 1
- 1
- 1 1
- 4 4 2 5 7 2 3 or 4 4 2 5 7 2 3

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given $$$n$$$ integers, each integer is from $$$1$$$ to $$$n$$$, all of them are pairwise distinct. You have to paint them red and blue (each integer should have exactly one color).

The cost of painting is the number of pairs $$$(x, y)$$$ such that $$$y \bmod x = 0$$$, $$$y$$$ is red and $$$x$$$ is blue.

For each $$$k \in [1, n]$$$, calculate the maximum cost of painting if exactly $$$k$$$ integers should have a red color.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 10^5$$$).

## Output Format
For each $$$k \in [1,n]$$$ print one integer — the maximum cost of painting, if exactly $$$k$$$ integers should be red.

## Examples
```input
6
```
```output
3 5 6 6 5 0
```
-----
```input
2
```
```output
1 0
```
-----
```input
11
```
```output
3 6 9 11 12 13 14 14 13 10 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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 10.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an integer $$$n$$$ and a sequence $$$a$$$ of $$$n-1$$$ integers, each element is either $$$0$$$ or $$$1$$$.

You are asked to build a string of length $$$n$$$ such that:

- each letter is one of "abcd";
- if $$$a_i=1$$$, then the $$$i$$$-th suffix of the string is lexicographically smaller than the $$$(i+1)$$$-th suffix;
- if $$$a_i=0$$$, then the $$$i$$$-th suffix of the string is lexicographically greater than the $$$(i+1)$$$-th suffix.

You will be asked $$$q$$$ queries of form:

- $$$i$$$ ($$$1 \le i \le n - 1$$$) — flip the value of $$$a_i$$$ (if $$$a_i=0$$$, then set $$$a_i$$$ to $$$1$$$, and vice versa).

After each query print the number of different strings that satisfy the given constraints modulo $$$998\,244\,353$$$.

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

The second line contains $$$n-1$$$ integers $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$a_i \in \{0, 1\}$$$) — the constraints on suffixes of the string.

Each of the next $$$q$$$ lines contains a query: an integer $$$i$$$ ($$$1 \le i \le n - 1$$$) — flip the value of $$$a_i$$$ (if $$$a_i=0$$$, then set $$$a_i$$$ to $$$1$$$, and vice versa).

## Output Format
After each query print the number of different strings that satisfy the given constraints modulo $$$998\,244\,353$$$.

## Examples
```input
2 2
0
1
1
```
```output
6
10
```
-----
```input
3 4
0 0
1
2
1
2
```
```output
20
10
14
20
```
-----
```input
10 10
0 0 0 1 1 1 0 1 0
4
1
8
4
2
9
5
6
6
8
```
```output
1815
3201
2710
2776
2290
1644
2668
1271
2668
2436
```

## Note
The $$$i$$$-th suffix of a string is a continuous substring that starts from the $$$i$$$-th position and ends in the last position.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

Two strings $$$a$$$ and $$$b$$$ of length $$$n$$$ differ if there exists a position $$$i$$$ such that $$$a_i \neq b_i$$$.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarp calls an array dense if the greater of any two adjacent elements is not more than twice bigger than the smaller. More formally, for any $$$i$$$ ($$$1 \le i \le n-1$$$), this condition must be satisfied: $$$$$$\frac{\max(a[i], a[i+1])}{\min(a[i], a[i+1])} \le 2$$$$$$

For example, the arrays $$$[1, 2, 3, 4, 3]$$$, $$$[1, 1, 1]$$$ and $$$[5, 10]$$$ are dense. And the arrays $$$[5, 11]$$$, $$$[1, 4, 2]$$$, $$$[6, 6, 1]$$$ are not dense.

You are given an array $$$a$$$ of $$$n$$$ integers. What is the minimum number of numbers you need to add to an array to make it dense? You can insert numbers anywhere in the array. If the array is already dense, no numbers need to be added.

For example, if $$$a=[4,2,10,1]$$$, then the answer is $$$5$$$, and the array itself after inserting elements into it may look like this: $$$a=[4,2,\underline{\textbf{3}},\underline{\textbf{5}},10,\underline{\textbf{6}},\underline{\textbf{4}},\underline{\textbf{2}},1]$$$ (there are other ways to build such $$$a$$$).

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$). Then $$$t$$$ test cases follow.

The first line of each test case contains one integer $$$n$$$ ($$$2 \le n \le 50$$$) — the length of the array $$$a$$$.

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 50$$$).

## Output Format
For each test case, output one integer — the minimum number of numbers that must be added to the array to make it dense.

## Examples
```input
6
4
4 2 10 1
2
1 3
2
6 1
3
1 4 2
5
1 2 3 4 3
12
4 31 25 50 30 20 34 46 42 16 15 16
```
```output
5
1
2
1
0
3
```

## Note
The first test case is explained in the statements.

In the second test case, you can insert one element, $$$a=[1,\underline{\textbf{2}},3]$$$.

In the third test case, you can insert two elements, $$$a=[6,\underline{\textbf{4}},\underline{\textbf{2}},1]$$$.

In the fourth test case, you can insert one element, $$$a=[1,\underline{\textbf{2}},4,2]$$$.

In the fifth test case, the array $$$a$$$ is already dense.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a positive integer $$$x$$$. Check whether the number $$$x$$$ is representable as the sum of the cubes of two positive integers.

Formally, you need to check if there are two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b$$$) such that $$$a^3+b^3=x$$$.

For example, if $$$x = 35$$$, then the numbers $$$a=2$$$ and $$$b=3$$$ are suitable ($$$2^3+3^3=8+27=35$$$). If $$$x=4$$$, then no pair of numbers $$$a$$$ and $$$b$$$ is suitable.

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

Each test case contains one integer $$$x$$$ ($$$1 \le x \le 10^{12}$$$).

Please note, that the input for some test cases won't fit into $$$32$$$-bit integer type, so you should use at least $$$64$$$-bit integer type in your programming language.

## Output Format
For each test case, output on a separate line:

- "YES" if $$$x$$$ is representable as the sum of the cubes of two positive integers.
- "NO" otherwise.

You can output "YES" and "NO" in any case (for example, the strings yEs, yes, Yes and YES will be recognized as positive).

## Examples
```input
7
1
2
4
34
35
16
703657519796
```
```output
NO
YES
NO
NO
YES
YES
YES
```

## Note
The number $$$1$$$ is not representable as the sum of two cubes.

The number $$$2$$$ is represented as $$$1^3+1^3$$$.

The number $$$4$$$ is not representable as the sum of two cubes.

The number $$$34$$$ is not representable as the sum of two cubes.

The number $$$35$$$ is represented as $$$2^3+3^3$$$.

The number $$$16$$$ is represented as $$$2^3+2^3$$$.

The number $$$703657519796$$$ is represented as $$$5779^3+7993^3$$$.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
A permutation — is a sequence of length $$$n$$$ integers from $$$1$$$ to $$$n$$$, in which all the numbers occur exactly once. For example, $$$[1]$$$, $$$[3, 5, 2, 1, 4]$$$, $$$[1, 3, 2]$$$ — permutations, and $$$[2, 3, 2]$$$, $$$[4, 3, 1]$$$, $$$[0]$$$ — no.

Polycarp was recently gifted a permutation $$$a[1 \dots n]$$$ of length $$$n$$$. Polycarp likes trees more than permutations, so he wants to transform permutation $$$a$$$ into a rooted binary tree. He transforms an array of different integers into a tree as follows:

- the maximum element of the array becomes the root of the tree;
- all elements to the left of the maximum — form a left subtree (which is built according to the same rules but applied to the left part of the array), but if there are no elements to the left of the maximum, then the root has no left child;
- all elements to the right of the maximum — form a right subtree (which is built according to the same rules but applied to the right side of the array), but if there are no elements to the right of the maximum, then the root has no right child.

For example, if he builds a tree by permutation $$$a=[3, 5, 2, 1, 4]$$$, then the root will be the element $$$a_2=5$$$, and the left subtree will be the tree that will be built for the subarray $$$a[1 \dots 1] = [3]$$$, and the right one — for the subarray $$$a[3 \dots 5] = [2, 1, 4]$$$. As a result, the following tree will be built:

The tree corresponding to the permutation $$$a=[3, 5, 2, 1, 4]$$$.

Another example: let the permutation be $$$a=[1, 3, 2, 7, 5, 6, 4]$$$. In this case, the tree looks like this:

The tree corresponding to the permutation $$$a=[1, 3, 2, 7, 5, 6, 4]$$$.

Let us denote by $$$d_v$$$ the depth of the vertex $$$a_v$$$, that is, the number of edges on the path from the root to the vertex numbered $$$a_v$$$. Note that the root depth is zero. Given the permutation $$$a$$$, for each vertex, find the value of $$$d_v$$$.

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

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

This is followed by $$$n$$$ numbers $$$a_1, a_2, \ldots, a_n$$$ — permutation $$$a$$$.

## Output Format
For each test case, output $$$n$$$ values — $$$d_1, d_2, \ldots, d_n$$$.

## Examples
```input
3
5
3 5 2 1 4
1
1
4
4 3 1 2
```
```output
1 0 2 3 1 
0 
0 1 3 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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
A championship is held in Berland, in which $$$n$$$ players participate. The player with the number $$$i$$$ has $$$a_i$$$ ($$$a_i \ge 1$$$) tokens.

The championship consists of $$$n-1$$$ games, which are played according to the following rules:

- in each game, two random players with non-zero tokens are selected;
- the player with more tokens is considered the winner of the game (in case of a tie, the winner is chosen randomly);
- the winning player takes all of the loser's tokens;

The last player with non-zero tokens is the winner of the championship.

All random decisions that are made during the championship are made equally probable and independently.

For example, if $$$n=4$$$, $$$a = [1, 2, 4, 3]$$$, then one of the options for the game (there could be other options) is:

- during the first game, the first and fourth players were selected. The fourth player has more tokens, so he takes the first player's tokens. Now $$$a = [0, 2, 4, 4]$$$;
- during the second game, the fourth and third players were selected. They have the same number of tokens, but in a random way, the third player is the winner. Now $$$a = [0, 2, 8, 0]$$$;
- during the third game, the second and third players were selected. The third player has more tokens, so he takes the second player's tokens. Now $$$a = [0, 0, 10, 0]$$$;
- the third player is declared the winner of the championship.

Championship winners will receive personalized prizes. Therefore, the judges want to know in advance which players have a chance of winning, i.e have a non-zero probability of winning the championship. You have been asked to find all such players.

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

The first line of each test case consists of one positive integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of players in the championship.

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 number of tokens the players have.

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 the number of players who have a nonzero probability of winning the championship. On the next line print the numbers of these players in increasing order. Players are numbered starting from one in the order in which they appear in the input.

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

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarp was gifted an array $$$a$$$ of length $$$n$$$. Polycarp considers an array beautiful if there exists a number $$$C$$$, such that each number in the array occurs either zero or $$$C$$$ times. Polycarp wants to remove some elements from the array $$$a$$$ to make it beautiful.

For example, if $$$n=6$$$ and $$$a = [1, 3, 2, 1, 4, 2]$$$, then the following options are possible to make the array $$$a$$$ array beautiful:

- Polycarp removes elements at positions $$$2$$$ and $$$5$$$, array $$$a$$$ becomes equal to $$$[1, 2, 1, 2]$$$;
- Polycarp removes elements at positions $$$1$$$ and $$$6$$$, array $$$a$$$ becomes equal to $$$[3, 2, 1, 4]$$$;
- Polycarp removes elements at positions $$$1, 2$$$ and $$$6$$$, array $$$a$$$ becomes equal to $$$[2, 1, 4]$$$;

Help Polycarp determine the minimum number of elements to remove from the array $$$a$$$ to make it beautiful.

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

The first line of each test case consists of one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 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 10^9$$$) — array $$$a$$$.

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 one integer — the minimum number of elements that Polycarp has to remove from the array $$$a$$$ to make it beautiful.

## Examples
```input
3
6
1 3 2 1 4 2
4
100 100 4 100
8
1 2 3 3 3 2 6 6
```
```output
2
1
2
```

Now solve the problem and return the code.