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

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
BerSoft is the biggest IT corporation in Berland. There are $$$n$$$ employees at BerSoft company, numbered from $$$1$$$ to $$$n$$$.

The first employee is the head of the company, and he does not have any superiors. Every other employee $$$i$$$ has exactly one direct superior $$$p_i$$$.

Employee $$$x$$$ is considered to be a superior (direct or indirect) of employee $$$y$$$ if one of the following conditions holds:

- employee $$$x$$$ is the direct superior of employee $$$y$$$;
- employee $$$x$$$ is a superior of the direct superior of employee $$$y$$$.

The structure of BerSoft is organized in such a way that the head of the company is superior of every employee.

A programming competition is going to be held soon. Two-person teams should be created for this purpose. However, if one employee in a team is the superior of another, they are uncomfortable together. So, teams of two people should be created so that no one is the superior of the other. Note that no employee can participate in more than one team.

Your task is to calculate the maximum possible number of teams according to the aforementioned rules.

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

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

The second line contains $$$n-1$$$ integers $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i \le n$$$), where $$$p_i$$$ is the index of the direct superior of the $$$i$$$-th employee.

The sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the maximum possible number of teams according to the aforementioned rules.

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

## Note
In the first test case, team $$$(3, 4)$$$ can be created.

In the second test case, no team can be created, because there are only $$$2$$$ employees and one is the superior of another.

In the third test case, team $$$(2, 3)$$$ can be created.

In the fourth test case, teams $$$(2, 4)$$$, $$$(3, 5)$$$ and $$$(6, 7)$$$ can be created.

In the fifth test case, teams $$$(2, 3)$$$, $$$(6, 4)$$$ and $$$(5, 7)$$$ can be created.

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
Alex is solving a problem. He has $$$n$$$ constraints on what the integer $$$k$$$ can be. There are three types of constraints:

1. $$$k$$$ must be greater than or equal to some integer $$$x$$$;
2. $$$k$$$ must be less than or equal to some integer $$$x$$$;
3. $$$k$$$ must be not equal to some integer $$$x$$$.

Help Alex find the number of integers $$$k$$$ that satisfy all $$$n$$$ constraints. It is guaranteed that the answer is finite (there exists at least one constraint of type $$$1$$$ and at least one constraint of type $$$2$$$). Also, it is guaranteed that no two constraints are the exact same.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 100$$$) — the number of constraints.

The following $$$n$$$ lines describe the constraints. Each line contains two integers $$$a$$$ and $$$x$$$ ($$$a \in \{1,2,3\}, \, 1 \leq x \leq 10^9$$$). $$$a$$$ denotes the type of constraint. If $$$a=1$$$, $$$k$$$ must be greater than or equal to $$$x$$$. If $$$a=2$$$, $$$k$$$ must be less than or equal to $$$x$$$. If $$$a=3$$$, $$$k$$$ must be not equal to $$$x$$$.

It is guaranteed that there is a finite amount of integers satisfying all $$$n$$$ constraints (there exists at least one constraint of type $$$1$$$ and at least one constraint of type $$$2$$$). It is also guaranteed that no two constraints are the exact same (in other words, all pairs $$$(a, x)$$$ are distinct).

## Output Format
For each test case, output a single integer — the number of integers $$$k$$$ that satisfy all $$$n$$$ constraints.

## Examples
```input
6
4
1 3
2 10
3 1
3 5
2
1 5
2 4
10
3 6
3 7
1 2
1 7
3 100
3 44
2 100
2 98
1 3
3 99
6
1 5
2 10
1 9
2 2
3 2
3 9
5
1 1
2 2
3 1
3 2
3 3
6
1 10000
2 900000000
3 500000000
1 100000000
3 10000
3 900000001
```
```output
7
0
90
0
0
800000000
```

## Note
In the first test case, $$$k \geq 3$$$ and $$$k \leq 10$$$. Furthermore, $$$k \neq 1$$$ and $$$k \neq 5$$$. The possible integers $$$k$$$ that satisfy the constraints are $$$3,4,6,7,8,9,10$$$. So the answer is $$$7$$$.

In the second test case, $$$k \ge 5$$$ and $$$k \le 4$$$, which is impossible. So the answer is $$$0$$$.

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Alice and Bob are playing a game. They have an array $$$a_1, a_2,\ldots,a_n$$$. The game consists of two steps:

- First, Alice will remove at most $$$k$$$ elements from the array.
- Second, Bob will multiply at most $$$x$$$ elements of the array by $$$-1$$$.

Alice wants to maximize the sum of elements of the array while Bob wants to minimize it. Find the sum of elements of the array after the game if both players play optimally.

## Input Format
Each test consists of 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 three integers $$$n$$$, $$$k$$$, and $$$x$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq x,k \leq n$$$) — the number of elements in the array, the limit on the number of elements of the array that Alice can remove, and the limit on the number of elements of the array that Bob can multiply $$$-1$$$ to.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2,\ldots, a_n$$$ ($$$1 \leq a_i \leq 1000$$$) — the 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, output a single integer — the sum of elements of the array after the game if both players play optimally.

## Examples
```input
8
1 1 1
1
4 1 1
3 1 2 4
6 6 3
1 4 3 2 5 6
6 6 1
3 7 3 3 32 15
8 5 3
5 5 3 3 3 2 9 9
10 6 4
1 8 2 9 3 3 4 5 3 200
2 2 1
4 3
2 1 2
1 3
```
```output
0
2
0
3
-5
-9
0
-1
```

## Note
In the first test case, it is optimal for Alice to remove the only element of the array. Then, the sum of elements of the array is $$$0$$$ after the game is over.

In the second test case, it is optimal for Alice to not remove any elements. Bob will then multiply $$$4$$$ by $$$-1$$$. So the final sum of elements of the array is $$$3+1+2-4=2$$$.

In the fifth test case, it is optimal for Alice to remove $$$9, 9$$$. Bob will then multiply $$$5, 5, 3$$$ by $$$-1$$$. So the final sum of elements of the array is $$$-5-5-3+3+3+2=-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 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
Allen has an array $$$a_1, a_2,\ldots,a_n$$$. For every positive integer $$$k$$$ that is a divisor of $$$n$$$, Allen does the following:

- He partitions the array into $$$\frac{n}{k}$$$ disjoint subarrays of length $$$k$$$. In other words, he partitions the array into the following subarrays: $$$$$$[a_1,a_2,\ldots,a_k],[a_{k+1}, a_{k+2},\ldots,a_{2k}],\ldots,[a_{n-k+1},a_{n-k+2},\ldots,a_{n}]$$$$$$
- Allen earns one point if there exists some positive integer $$$m$$$ ($$$m \geq 2$$$) such that if he replaces every element in the array with its remainder when divided by $$$m$$$, then all subarrays will be identical.

Help Allen find the number of points he will earn.

## Input Format
Each test consists of 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 integer $$$n$$$ ($$$1 \leq n \leq 2\cdot10^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 \leq a_i \leq n$$$) — the elements of the 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 a single integer — the number of points Allen will earn.

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

## Note
In the first test case, $$$k=2$$$ earns a point since Allen can pick $$$m = 2$$$ and both subarrays will be equal to $$$[1, 0]$$$. $$$k=4$$$ also earns a point, since no matter what $$$m$$$ Allen chooses, there will be only one subarray and thus all subarrays are equal.

In the second test case, Allen earns $$$1$$$ point for $$$k=3$$$, where his choice for $$$m$$$ does not matter.

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

# Problem
Patrick calls a substring$$$^\dagger$$$ of a binary string$$$^\ddagger$$$ good if this substring contains exactly one 1.

Help Patrick count the number of binary strings $$$s$$$ such that $$$s$$$ contains exactly $$$n$$$ good substrings and has no good substring of length strictly greater than $$$k$$$. Note that substrings are differentiated by their location in the string, so if $$$s =$$$ 1010 you should count both occurrences of 10.

$$$^\dagger$$$ A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

$$$^\ddagger$$$ A binary string is a string that only contains the characters 0 and 1.

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

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2500$$$, $$$1 \leq k \leq n$$$) — the number of required good substrings and the maximum allowed length of a good substring.

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

## Output Format
For each test case, output a single integer — the number of binary strings $$$s$$$ such that $$$s$$$ contains exactly $$$n$$$ good substrings and has no good substring of length strictly greater than $$$k$$$. Since this integer can be too large, output it modulo $$$998\,244\,353$$$.

## Examples
```input
6
1 1
3 2
4 2
5 4
6 2
2450 2391
```
```output
1
3
5
12
9
259280854
```

## Note
In the first test case, the only suitable binary string is 1. String 01 is not suitable because it contains a substring 01 with length $$$2 > 1$$$.

In the second test case, suitable binary strings are 011, 110 and 111.

In the third test case, suitable binary strings are 101, 0110, 0111, 1110, and 1111.

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
Jay managed to create a problem of difficulty $$$x$$$ and decided to make it the second problem for Codeforces Round #921.

But Yash fears that this problem will make the contest highly unbalanced, and the coordinator will reject it. So, he decided to break it up into a problemset of $$$n$$$ sub-problems such that the difficulties of all the sub-problems are a positive integer and their sum is equal to $$$x$$$.

The coordinator, Aleksey, defines the balance of a problemset as the GCD of the difficulties of all sub-problems in the problemset.

Find the maximum balance that Yash can achieve if he chooses the difficulties of the sub-problems optimally.

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

Each test case contains a single line of input containing two integers $$$x$$$ ($$$1\leq x\leq 10^8$$$) and $$$n$$$ ($$$1\leq n\leq x$$$).

## Output Format
For each test case, print a single line containing a single integer denoting the maximum balance of the problemset Yash can achieve.

## Examples
```input
3
10 3
5 5
420 69
```
```output
2
1
6
```

## Note
For the first test case, one possible way is to break up the problem of difficulty $$$10$$$ into a problemset having three problems of difficulties $$$4$$$, $$$2$$$ and $$$4$$$ respectively, giving a balance equal to $$$2$$$.

For the second test case, there is only one way to break up the problem of difficulty $$$5$$$ into a problemset of $$$5$$$ problems with each problem having a difficulty $$$1$$$ giving a balance equal to $$$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
Fox loves permutations! She came up with the following problem and asked Cat to solve it:

You are given an even positive integer $$$n$$$ and a permutation$$$^\dagger$$$ $$$p$$$ of length $$$n$$$.

The score of another permutation $$$q$$$ of length $$$n$$$ is the number of local maximums in the array $$$a$$$ of length $$$n$$$, where $$$a_i = p_i + q_i$$$ for all $$$i$$$ ($$$1 \le i \le n$$$). In other words, the score of $$$q$$$ is the number of $$$i$$$ such that $$$1 < i < n$$$ (note the strict inequalities), $$$a_{i-1} < a_i$$$, and $$$a_i > a_{i+1}$$$ (once again, note the strict inequalities).

Find the permutation $$$q$$$ that achieves the maximum score for given $$$n$$$ and $$$p$$$. If there exist multiple such permutations, you can pick any of them.

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

## Input Format
The first line of input contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases in the input you will have to solve.

The first line of each test case contains one even integer $$$n$$$ ($$$4 \leq n \leq 10^5$$$, $$$n$$$ is even) — the length of the permutation $$$p$$$.

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

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

## Output Format
For each test case, output one line containing any permutation of length $$$n$$$ (the array $$$q$$$), such that $$$q$$$ maximizes the score under the given constraints.

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

## Note
In the first example, $$$a = [3, 6, 4, 7]$$$. The array has just one local maximum (on the second position), so the score of the chosen permutation $$$q$$$ is $$$1$$$. It can be proven that this score is optimal under the constraints.

In the last example, the resulting array $$$a = [6, 6, 12, 7, 14, 7, 14, 6]$$$ has $$$3$$$ local maximums — on the third, fifth and seventh 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
You are given two integer arrays: array $$$a$$$ of length $$$n$$$ and array $$$b$$$ of length $$$n+1$$$.

You can perform the following operations any number of times in any order:

- choose any element of the array $$$a$$$ and increase it by $$$1$$$;
- choose any element of the array $$$a$$$ and decrease it by $$$1$$$;
- choose any element of the array $$$a$$$, copy it and append the copy to the end of the array $$$a$$$.

Your task is to calculate the minimum number of aforementioned operations (possibly zero) required to transform the array $$$a$$$ into the array $$$b$$$. It can be shown that under the constraints of the problem, it is always possible.

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

Each test case consists of three lines:

- the first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$);
- the second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$);
- the third line contains $$$n + 1$$$ integers $$$b_1, b_2, \dots, b_{n + 1}$$$ ($$$1 \le b_i \le 10^9$$$).

Additional constraint on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the minimum number of operations (possibly zero) required to transform the array $$$a$$$ into the array $$$b$$$.

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

## Note
In the first example, you can transform $$$a$$$ into $$$b$$$ as follows: $$$[2] \rightarrow [2, 2] \rightarrow [1, 2] \rightarrow [1, 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 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
A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters '1' and '+' between the original characters of the sequence. For example:

- bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)");
- bracket sequences ")(", "(" and ")" are not.

Let's define the inverse of the bracket sequence as follows: replace all brackets '(' with ')', and vice versa (all brackets ')' with '('). For example, strings "()((" and ")())" are inverses of each other.

You are given a regular bracket sequence $$$s$$$. Calculate the number of pairs of integers $$$(l,r)$$$ ($$$1 \le l \le r \le |s|$$$) such that if you replace the substring of $$$s$$$ from the $$$l$$$-th character to the $$$r$$$-th character (inclusive) with its inverse, $$$s$$$ will still be a regular bracket sequence.

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

The only line of each test case contains a non-empty regular bracket sequence; it consists only of characters '(' and/or ')'.

Additional constraint on the input: the total length of the regular bracket sequences over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the number of pairs $$$(l,r)$$$ meeting the conditions from the statement.

## Examples
```input
4
(())
()
()()()
(()())(())
```
```output
1
0
3
13
```

## Note
In the first example, there is only one pair:

- $$$(2, 3)$$$: (()) $$$\rightarrow$$$ ()().

In the second example, there are no pairs.

In the third example, there are three pairs:

- $$$(2, 3)$$$: ()()() $$$\rightarrow$$$ (())();
- $$$(4, 5)$$$: ()()() $$$\rightarrow$$$ ()(());
- $$$(2, 5)$$$: ()()() $$$\rightarrow$$$ (()());

Now solve the problem and return the code.