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

# Problem
Andrew has $$$n$$$ piles with stones. The $$$i$$$-th pile contains $$$a_i$$$ stones. He wants to make his table clean so he decided to put every stone either to the $$$1$$$-st or the $$$n$$$-th pile.

Andrew can perform the following operation any number of times: choose $$$3$$$ indices $$$1 \le i < j < k \le n$$$, such that the $$$j$$$-th pile contains at least $$$2$$$ stones, then he takes $$$2$$$ stones from the pile $$$j$$$ and puts one stone into pile $$$i$$$ and one stone into pile $$$k$$$.

Tell Andrew what is the minimum number of operations needed to move all the stones to piles $$$1$$$ and $$$n$$$, or determine if it's impossible.

## Input Format
The input contains several test cases. The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — the number of test cases.

The first line for each test case contains one integer $$$n$$$ ($$$3 \leq n \leq 10^5$$$) — the length of the array.

The second line contains a sequence of integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the array elements.

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

## Output Format
For each test case print the minimum number of operations needed to move stones to piles $$$1$$$ and $$$n$$$, or print $$$-1$$$ if it's impossible.

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

## Note
In the first test case, it is optimal to do the following:

1. Select $$$(i, j, k) = (1, 2, 5)$$$. The array becomes equal to $$$[2, 0, 2, 3, 7]$$$.
2. Select $$$(i, j, k) = (1, 3, 4)$$$. The array becomes equal to $$$[3, 0, 0, 4, 7]$$$.
3. Twice select $$$(i, j, k) = (1, 4, 5)$$$. The array becomes equal to $$$[5, 0, 0, 0, 9]$$$. This array satisfy the statement, because every stone is moved to piles $$$1$$$ and $$$5$$$.

In the second test case, it's impossible to put all stones into piles with numbers $$$1$$$ and $$$3$$$:

1. At the beginning there's only one possible operation with $$$(i, j, k) = (1, 2, 3)$$$. The array becomes equal to $$$[2, 1, 2]$$$.
2. Now there is no possible operation and the array doesn't satisfy the statement, so the answer is $$$-1$$$.

In the third test case, it's optimal to do the following:

1. Select $$$(i, j, k) = (1, 2, 3)$$$. The array becomes equal to $$$[2, 0, 2]$$$. This array satisfies the statement, because every stone is moved to piles $$$1$$$ and $$$3$$$.

In the fourth test case, it's impossible to do any operation, and the array doesn't satisfy the statement, so the 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 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 two arrays $$$a$$$ and $$$b$$$, both of length $$$n$$$.

You can perform the following operation any number of times (possibly zero): select an index $$$i$$$ ($$$1 \leq i \leq n$$$) and swap $$$a_i$$$ and $$$b_i$$$.

Let's define the cost of the array $$$a$$$ as $$$\sum_{i=1}^{n} \sum_{j=i + 1}^{n} (a_i + a_j)^2$$$. Similarly, the cost of the array $$$b$$$ is $$$\sum_{i=1}^{n} \sum_{j=i + 1}^{n} (b_i + b_j)^2$$$.

Your task is to minimize the total cost of two arrays.

## Input Format
Each test case consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 40$$$) — the number of test cases. The following is a description of the input data sets.

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

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

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 100$$$) — elements of the second array.

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

## Output Format
For each test case, print the minimum possible total cost.

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

## Note
In the second test case, in one of the optimal answers after all operations $$$a = [2, 6, 4, 6]$$$, $$$b = [3, 7, 6, 1]$$$.

The cost of the array $$$a$$$ equals to $$$(2 + 6)^2 + (2 + 4)^2 + (2 + 6)^2 + (6 + 4)^2 + (6 + 6)^2 + (4 + 6)^2 = 508$$$.

The cost of the array $$$b$$$ equals to $$$(3 + 7)^2 + (3 + 6)^2 + (3 + 1)^2 + (7 + 6)^2 + (7 + 1)^2 + (6 + 1)^2 = 479$$$.

The total cost of two arrays equals to $$$508 + 479 = 987$$$.

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 an array $$$a$$$ of length $$$n$$$. Let $$$cnt_x$$$ be the number of elements from the array which are equal to $$$x$$$. Let's also define $$$f(x, y)$$$ as $$$(cnt_x + cnt_y) \cdot (x + y)$$$.

Also you are given $$$m$$$ bad pairs $$$(x_i, y_i)$$$. Note that if $$$(x, y)$$$ is a bad pair, then $$$(y, x)$$$ is also bad.

Your task is to find the maximum value of $$$f(u, v)$$$ over all pairs $$$(u, v)$$$, such that $$$u \neq v$$$, that this pair is not bad, and also that $$$u$$$ and $$$v$$$ each occur in the array $$$a$$$. It is guaranteed that such a pair exists.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 3 \cdot 10^5$$$, $$$0 \le m \le 3 \cdot 10^5$$$) — the length of the array and the number of bad pairs.

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

The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i < y_i \le 10^9$$$), which represent a bad pair. It is guaranteed that no bad pair occurs twice in the input. It is also guaranteed that $$$cnt_{x_i} > 0$$$ and $$$cnt_{y_i} > 0$$$.

It is guaranteed that for each test case there is a pair of integers $$$(u, v)$$$, $$$u \ne v$$$, that is not bad, and such that both of these numbers occur in $$$a$$$.

It is guaranteed that the total sum of $$$n$$$ and the total sum of $$$m$$$ don't exceed $$$3 \cdot 10^5$$$.

## Output Format
For each test case print a single integer — the answer to the problem.

## Examples
```input
3
6 1
6 3 6 7 3 3
3 6
2 0
3 4
7 4
1 2 2 3 1 5 1
1 5
3 5
1 3
2 5
```
```output
40
14
15
```

## Note
In the first test case $$$3$$$, $$$6$$$, $$$7$$$ occur in the array.

- $$$f(3, 6) = (cnt_3 + cnt_6) \cdot (3 + 6) = (3 + 2) \cdot (3 + 6) = 45$$$. But $$$(3, 6)$$$ is bad so we ignore it.
- $$$f(3, 7) = (cnt_3 + cnt_7) \cdot (3 + 7) = (3 + 1) \cdot (3 + 7) = 40$$$.
- $$$f(6, 7) = (cnt_6 + cnt_7) \cdot (6 + 7) = (2 + 1) \cdot (6 + 7) = 39$$$.

The answer to the problem is $$$\max(40, 39) = 40$$$.

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 tree with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. The height of the $$$i$$$-th vertex is $$$h_i$$$. You can place any number of towers into vertices, for each tower you can choose which vertex to put it in, as well as choose its efficiency. Setting up a tower with efficiency $$$e$$$ costs $$$e$$$ coins, where $$$e > 0$$$.

It is considered that a vertex $$$x$$$ gets a signal if for some pair of towers at the vertices $$$u$$$ and $$$v$$$ ($$$u \neq v$$$, but it is allowed that $$$x = u$$$ or $$$x = v$$$) with efficiencies $$$e_u$$$ and $$$e_v$$$, respectively, it is satisfied that $$$\min(e_u, e_v) \geq h_x$$$ and $$$x$$$ lies on the path between $$$u$$$ and $$$v$$$.

Find the minimum number of coins required to set up towers so that you can get a signal at all vertices.

## Input Format
The first line contains an integer $$$n$$$ ($$$2 \le n \le 200\,000$$$) — the number of vertices in the tree.

The second line contains $$$n$$$ integers $$$h_i$$$ ($$$1 \le h_i \le 10^9$$$) — the heights of the vertices.

Each of the next $$$n - 1$$$ lines contain a pair of numbers $$$v_i, u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — an edge of the tree. It is guaranteed that the given edges form a tree.

## Output Format
Print one integer — the minimum required number of coins.

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

## Note
In the first test case it's optimal to install two towers with efficiencies $$$2$$$ at vertices $$$1$$$ and $$$3$$$.

In the second test case it's optimal to install a tower with efficiency $$$1$$$ at vertex $$$1$$$ and two towers with efficiencies $$$3$$$ at vertices $$$2$$$ and $$$5$$$.

In the third test case it's optimal to install two towers with efficiencies $$$6$$$ at vertices $$$1$$$ and $$$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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Vitaly gave Maxim $$$n$$$ numbers $$$1, 2, \ldots, n$$$ for his $$$16$$$-th birthday. Maxim was tired of playing board games during the celebration, so he decided to play with these numbers. In one step Maxim can choose two numbers $$$x$$$ and $$$y$$$ from the numbers he has, throw them away, and add two numbers $$$x + y$$$ and $$$|x - y|$$$ instead. He wants all his numbers to be equal after several steps and the sum of the numbers to be minimal.

Help Maxim to find a solution. Maxim's friends don't want to wait long, so the number of steps in the solution should not exceed $$$20n$$$. It is guaranteed that under the given constraints, if a solution exists, then there exists a solution that makes all numbers equal, minimizes their sum, and spends no more than $$$20n$$$ moves.

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

Each test case contains a single integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^4$$$) — the number of integers given to Maxim.

It is guaranteed that the total sum of $$$n$$$ doesn't exceed $$$5 \cdot 10^4$$$.

## Output Format
For each test case print $$$-1$$$ if it's impossible to make all numbers equal.

Otherwise print a single integer $$$s$$$ ($$$0 \le s \le 20n$$$) — the number of steps. Then print $$$s$$$ lines. The $$$i$$$-th line must contain two integers $$$x_i$$$ and $$$y_i$$$ — numbers that Maxim chooses on the $$$i$$$-th step. The numbers must become equal after all operations.

Don't forget that you not only need to make all numbers equal, but also minimize their sum. It is guaranteed that under the given constraints, if a solution exists, then there exists a solution that makes all numbers equal, minimizes their sum, and spends no more than $$$20n$$$ moves.

## Examples
```input
2
2
3
```
```output
-1
3
1 3
2 2
4 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a permutation $$$p$$$ of length $$$n$$$.

You can choose any subsequence, remove it from the permutation, and insert it at the beginning of the permutation keeping the same order.

For every $$$k$$$ from $$$0$$$ to $$$n$$$, find the minimal possible number of inversions in the permutation after you choose a subsequence of length exactly $$$k$$$.

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

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

The second line of each test case contains the permutation $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$).

It is guaranteed that the total sum of $$$n$$$ doesn't exceed $$$5 \cdot 10^5$$$.

## Output Format
For each test case output $$$n + 1$$$ integers. The $$$i$$$-th of them must be the answer for the subsequence length of $$$i - 1$$$.

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

## Note
In the second test case:

- For the length $$$0$$$: $$$[4, 2, 1, 3] \rightarrow [4, 2, 1, 3]$$$: $$$4$$$ inversions.
- For the length $$$1$$$: $$$[4, 2, \mathbf{1}, 3] \rightarrow [1, 4, 2, 3]$$$: $$$2$$$ inversions.
- For the length $$$2$$$: $$$[4, \mathbf{2}, \mathbf{1}, 3] \rightarrow [2, 1, 4, 3]$$$, or $$$[4, 2, \mathbf{1}, \textbf{3}] \rightarrow [1, 3, 4, 2]$$$: $$$2$$$ inversions.
- For the length $$$3$$$: $$$[4, \mathbf{2}, \mathbf{1}, \mathbf{3}] \rightarrow [2, 1, 3, 4]$$$: $$$1$$$ inversion.
- For the length $$$4$$$: $$$[\mathbf{4}, \mathbf{2}, \mathbf{1}, \mathbf{3}] \rightarrow [4, 2, 1, 3]$$$: $$$4$$$ inversions.

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

# Problem
There are $$$n$$$ logs, the $$$i$$$-th log has a length of $$$a_i$$$ meters. Since chopping logs is tiring work, errorgorn and maomao90 have decided to play a game.

errorgorn and maomao90 will take turns chopping the logs with errorgorn chopping first. On his turn, the player will pick a log and chop it into $$$2$$$ pieces. If the length of the chosen log is $$$x$$$, and the lengths of the resulting pieces are $$$y$$$ and $$$z$$$, then $$$y$$$ and $$$z$$$ have to be positive integers, and $$$x=y+z$$$ must hold. For example, you can chop a log of length $$$3$$$ into logs of lengths $$$2$$$ and $$$1$$$, but not into logs of lengths $$$3$$$ and $$$0$$$, $$$2$$$ and $$$2$$$, or $$$1.5$$$ and $$$1.5$$$.

The player who is unable to make a chop will be the loser. Assuming that both errorgorn and maomao90 play optimally, who will be the winner?

## Input Format
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$)  — 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 \leq n \leq 50$$$)  — the number of logs.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 50$$$)  — the lengths of the logs.

Note that there is no bound on the sum of $$$n$$$ over all test cases.

## Output Format
For each test case, print "errorgorn" if errorgorn wins or "maomao90" if maomao90 wins. (Output without quotes).

## Examples
```input
2
4
2 4 2 1
1
1
```
```output
errorgorn
maomao90
```

## Note
In the first test case, errorgorn will be the winner. An optimal move is to chop the log of length $$$4$$$ into $$$2$$$ logs of length $$$2$$$. After this there will only be $$$4$$$ logs of length $$$2$$$ and $$$1$$$ log of length $$$1$$$.

After this, the only move any player can do is to chop any log of length $$$2$$$ into $$$2$$$ logs of length $$$1$$$. After $$$4$$$ moves, it will be maomao90's turn and he will not be able to make a move. Therefore errorgorn will be the winner.

In the second test case, errorgorn will not be able to make a move on his first turn and will immediately lose, making maomao90 the winner.

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

# Problem
Let's call a string good if its length is at least $$$2$$$ and all of its characters are $$$\texttt{A}$$$ except for the last character which is $$$\texttt{B}$$$. The good strings are $$$\texttt{AB},\texttt{AAB},\texttt{AAAB},\ldots$$$. Note that $$$\texttt{B}$$$ is not a good string.

You are given an initially empty string $$$s_1$$$.

You can perform the following operation any number of times:

- Choose any position of $$$s_1$$$ and insert some good string in that position.

Given a string $$$s_2$$$, can we turn $$$s_1$$$ into $$$s_2$$$ after some number of operations?

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

The first line of each test case contains a single string $$$s_2$$$ ($$$1 \leq |s_2| \leq 2 \cdot 10^5$$$).

It is guaranteed that $$$s_2$$$ consists of only the characters $$$\texttt{A}$$$ and $$$\texttt{B}$$$.

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

## Output Format
For each test case, print "YES" (without quotes) if we can turn $$$s_1$$$ into $$$s_2$$$ after some number of operations, and "NO" (without quotes) otherwise.

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

## Examples
```input
4
AABAB
ABB
AAAAAAAAB
A
```
```output
YES
NO
YES
NO
```

## Note
In the first test case, we transform $$$s_1$$$ as such: $$$\varnothing \to \color{red}{\texttt{AAB}} \to \texttt{A}\color{red}{\texttt{AB}}\texttt{AB}$$$.

In the third test case, we transform $$$s_1$$$ as such: $$$\varnothing \to \color{red}{\texttt{AAAAAAAAB}}$$$.

In the second and fourth test case, it can be shown that it is impossible to turn $$$s_1$$$ into $$$s_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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array $$$a$$$ of length $$$n$$$. We define the equality of the array as the number of indices $$$1 \le i \le n - 1$$$ such that $$$a_i = a_{i + 1}$$$. We are allowed to do the following operation:

- Select two integers $$$i$$$ and $$$x$$$ such that $$$1 \le i \le n - 1$$$ and $$$1 \le x \le 10^9$$$. Then, set $$$a_i$$$ and $$$a_{i + 1}$$$ to be equal to $$$x$$$.

Find the minimum number of operations needed such that the equality of the array is less than or equal to $$$1$$$.

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

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10 ^ 5$$$) — the length of 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$$$) — elements of the array.

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

## Output Format
For each test case, print the minimum number of operations needed.

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

## Note
In the first test case, we can select $$$i=2$$$ and $$$x=2$$$ to form $$$[1, 2, 2, 1, 1]$$$. Then, we can select $$$i=3$$$ and $$$x=3$$$ to form $$$[1, 2, 3, 3, 1]$$$.

In the second test case, we can select $$$i=3$$$ and $$$x=100$$$ to form $$$[2, 1, 100, 100, 2]$$$.

Now solve the problem and return the code.