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

# Problem
There are $$$n$$$ equidistant antennas on a line, numbered from $$$1$$$ to $$$n$$$. Each antenna has a power rating, the power of the $$$i$$$-th antenna is $$$p_i$$$.

The $$$i$$$-th and the $$$j$$$-th antenna can communicate directly if and only if their distance is at most the minimum of their powers, i.e., $$$|i-j| \leq \min(p_i, p_j)$$$. Sending a message directly between two such antennas takes $$$1$$$ second.

What is the minimum amount of time necessary to send a message from antenna $$$a$$$ to antenna $$$b$$$, possibly using other antennas as relays?

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1\le t\le 100\,000$$$) — the number of test cases. The descriptions of the $$$t$$$ test cases follow.

The first line of each test case contains three integers $$$n$$$, $$$a$$$, $$$b$$$ ($$$1 \leq a, b \leq n \leq 200\,000$$$) — the number of antennas, and the origin and target antenna.

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — the powers of the antennas.

The sum of the values of $$$n$$$ over all test cases does not exceed $$$200\,000$$$.

## Output Format
For each test case, print the number of seconds needed to trasmit a message from $$$a$$$ to $$$b$$$. It can be shown that under the problem constraints, it is always possible to send such a message.

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

## Note
In the first test case, we must send a message from antenna $$$2$$$ to antenna $$$9$$$. A sequence of communications requiring $$$4$$$ seconds, which is the minimum possible amount of time, is the following:

- In $$$1$$$ second we send the message from antenna $$$2$$$ to antenna $$$1$$$. This is possible since $$$|2-1|\le \min(1, 4) = \min(p_2, p_1)$$$.
- In $$$1$$$ second we send the message from antenna $$$1$$$ to antenna $$$5$$$. This is possible since $$$|1-5|\le \min(4, 5) = \min(p_1, p_5)$$$.
- In $$$1$$$ second we send the message from antenna $$$5$$$ to antenna $$$10$$$. This is possible since $$$|5-10|\le \min(5, 5) = \min(p_5, p_{10})$$$.
- In $$$1$$$ second we send the message from antenna $$$10$$$ to antenna $$$9$$$. This is possible since $$$|10-9|\le \min(5, 1) = \min(p_{10}, p_9)$$$.

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
SWERC organizers want to hold a gastronomic event.

The location of the event is a building with $$$n$$$ rooms connected by $$$n-1$$$ corridors (each corridor connects two rooms) so that it is possible to go from any room to any other room.

In each room you have to set up the tasting of a typical Italian dish. You can choose from $$$n$$$ typical Italian dishes rated from $$$1$$$ to $$$n$$$ depending on how good they are ($$$n$$$ is the best possible rating). The $$$n$$$ dishes have distinct ratings.

You want to assign the $$$n$$$ dishes to the $$$n$$$ rooms so that the number of pleasing tours is maximal. A pleasing tour is a nonempty sequence of rooms so that:

- Each room in the sequence is connected to the next one in the sequence by a corridor.
- The ratings of the dishes in the rooms (in the order given by the sequence) are increasing.

## Input Format
The first line contains an integer $$$n$$$ ($$$2\le n\le 1\,000\,000$$$) — the number of rooms.

The second line contains $$$n-1$$$ integers $$$p_2, p_3, \cdots , p_n$$$ ($$$1 \leq p_i < i$$$). Each $$$p_i$$$ indicates that there is a corridor between room $$$i$$$ and room $$$p_i$$$. It is guaranteed that the building has the property that it is possible to go from any room to any other room.

## Output Format
Print the maximum number of pleasing tours.

## Examples
```input
5
1 2 2 2
```
```output
13
```
-----
```input
10
1 2 3 4 3 2 7 8 7
```
```output
47
```

## Note
In the first sample, it is optimal to place the dish with rating $$$1$$$ in room $$$1$$$, the dish with rating $$$2$$$ in room $$$3$$$, the dish with rating $$$3$$$ in room $$$2$$$, the dish with rating $$$4$$$ in room $$$5$$$ and the dish with rating $$$5$$$ in room $$$4$$$.

All the $$$13$$$ possible pleasing tours are: $$$(1)$$$, $$$(2)$$$, $$$(3)$$$, $$$(4)$$$, $$$(5)$$$, $$$(1,2)$$$, $$$(3,2)$$$, $$$(2,4)$$$, $$$(2,5)$$$, $$$(1,2,4)$$$, $$$(1,2,5)$$$, $$$(3,2,4)$$$, $$$(3,2,5)$$$.

There are also other ways to assign the dishes to the rooms so that there are $$$13$$$ pleasing tours.

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
Bethany would like to tile her bathroom. The bathroom has width $$$w$$$ centimeters and length $$$l$$$ centimeters. If Bethany simply used the basic tiles of size $$$1 \times 1$$$ centimeters, she would use $$$w \cdot l$$$ of them.

However, she has something different in mind.

- On the interior of the floor she wants to use the $$$1 \times 1$$$ tiles. She needs exactly $$$(w-2) \cdot (l-2)$$$ of these.
- On the floor boundary she wants to use tiles of size $$$1 \times a$$$ for some positive integer $$$a$$$. The tiles can also be rotated by $$$90$$$ degrees.

For which values of $$$a$$$ can Bethany tile the bathroom floor as described? Note that $$$a$$$ can also be $$$1$$$.

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

Each test case consist of a single line, which contains two integers $$$w$$$, $$$l$$$ ($$$3 \leq w, l \leq 10^{9}$$$) — the dimensions of the bathroom.

## Output Format
For each test case, print an integer $$$k$$$ ($$$0\le k$$$) — the number of valid values of $$$a$$$ for the given test case — followed by $$$k$$$ integers $$$a_1, a_2,\dots, a_k$$$ ($$$1\le a_i$$$) — the valid values of $$$a$$$. The values $$$a_1, a_2, \dots, a_k$$$ have to be sorted from smallest to largest.

It is guaranteed that under the problem constraints, the output contains at most $$$200\,000$$$ integers.

## Examples
```input
3
3 5
12 12
314159265 358979323
```
```output
3 1 2 3
3 1 2 11
2 1 2
```

## Note
In the first test case, the bathroom is $$$3$$$ centimeters wide and $$$5$$$ centimeters long. There are three values of $$$a$$$ such that Bethany can tile the floor as described in the statement, namely $$$a=1$$$, $$$a=2$$$ and $$$a=3$$$. The three tilings are represented in the following pictures.

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 a circular maze such as the ones shown in the figures.

- Circular walls are described by a radius $$$r$$$, the distance from the center, and two angles $$$\theta_1, \theta_2$$$ describing the beginning and the end of the wall in the clockwise direction. Notice that swapping the two angles changes the wall.
- Straight walls are described by an angle $$$\theta$$$, the direction of the wall, and two radii $$$r_1 < r_2$$$ describing the beginning and the end of the wall.

Angles are measured in degrees; the angle $$$0$$$ corresponds to the upward pointing direction; and angles increase clockwise (hence the east direction corresponds to the angle $$$90$$$).

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1\le t\le 20$$$) — the number of test cases. The descriptions of the $$$t$$$ test cases follow.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 5000$$$) — the number of walls.

Each of the following $$$n$$$ lines each contains a character (C for circular, and S for straight) and three integers:

- either $$$r, \theta_1, \theta_2$$$ ($$$1 \leq r \leq 20$$$ and $$$0 \leq \theta_1,\theta_2 < 360$$$ with $$$\theta_1 \neq \theta_2$$$) if the wall is circular,
- or $$$r_1$$$, $$$r_2$$$ and $$$\theta$$$ ($$$1 \leq r_1 < r_2 \leq 20$$$ and $$$0 \leq \theta < 360$$$) if the wall is straight.

It is guaranteed that circular walls do not overlap (but two circular walls may intersect at one or two points), and that straight walls do not overlap (but two straight walls may intersect at one point). However, circular and straight walls can intersect arbitrarily.

## Output Format
For each test case, print YES if the maze can be solved and NO otherwise.

## Examples
```input
2
5
C 1 180 90
C 5 250 230
C 10 150 140
C 20 185 180
S 1 20 180
6
C 1 180 90
C 5 250 230
C 10 150 140
C 20 185 180
S 1 20 180
S 5 10 0
```
```output
YES
NO
```

## Note
The two sample test cases correspond to the two mazes in the 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Ran Yakumo is a cute girl who loves creating cute Maths problems.

Let $$$f(x)$$$ be the minimal square number strictly greater than $$$x$$$, and $$$g(x)$$$ be the maximal square number less than or equal to $$$x$$$. For example, $$$f(1)=f(2)=g(4)=g(8)=4$$$.

A positive integer $$$x$$$ is cute if $$$x-g(x)<f(x)-x$$$. For example, $$$1,5,11$$$ are cute integers, while $$$3,8,15$$$ are not.

Ran gives you an array $$$a$$$ of length $$$n$$$. She wants you to find the smallest non-negative integer $$$k$$$ such that $$$a_i + k$$$ is a cute number for any element of $$$a$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — the length of $$$a$$$.

The second line contains $$$n$$$ intergers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_1 \leq a_2 \leq \ldots \leq a_n \leq 2\cdot 10^6$$$) — the array $$$a$$$.

## Output Format
Print a single interger $$$k$$$ — the answer.

## Examples
```input
4
1 3 8 10
```
```output
1
```
-----
```input
5
2 3 8 9 11
```
```output
8
```
-----
```input
8
1 2 3 4 5 6 7 8
```
```output
48
```

## Note
Test case 1:

$$$3$$$ is not cute integer, so $$$k\ne 0$$$.

$$$2,4,9,11$$$ are cute integers, so $$$k=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: 12.0 seconds
Memory limit: 1024.0 MB

# Problem
Koishi is unconsciously permuting $$$n$$$ numbers: $$$1, 2, \ldots, n$$$.

She thinks the permutation $$$p$$$ is beautiful if $$$s=\sum\limits_{i=1}^{n-1} [p_i+1=p_{i+1}]$$$. $$$[x]$$$ equals to $$$1$$$ if $$$x$$$ holds, or $$$0$$$ otherwise.

For each $$$k\in[0,n-1]$$$, she wants to know the number of beautiful permutations of length $$$n$$$ satisfying $$$k=\sum\limits_{i=1}^{n-1}[p_i<p_{i+1}]$$$.

## Input Format
There is one line containing two intergers $$$n$$$ ($$$1 \leq n \leq 250\,000$$$) and $$$s$$$ ($$$0 \leq s < n$$$).

## Output Format
Print one line with $$$n$$$ intergers. The $$$i$$$-th integers represents the answer of $$$k=i-1$$$, modulo $$$998244353$$$.

## Examples
```input
2 0
```
```output
1 0
```
-----
```input
4 1
```
```output
0 3 6 0
```
-----
```input
8 3
```
```output
0 0 0 35 770 980 70 0
```

## Note
Let $$$f(p)=\sum\limits_{i=1}^{n-1}[p_i<p_{i+1}]$$$.

Testcase 1:

$$$[2,1]$$$ is the only beautiful permutation. And $$$f([2,1])=0$$$.

Testcase 2:

Beautiful permutations:

$$$[1,2,4,3]$$$, $$$[1,3,4,2]$$$, $$$[1,4,2,3]$$$, $$$[2,1,3,4]$$$, $$$[2,3,1,4]$$$, $$$[3,1,2,4]$$$, $$$[3,4,2,1]$$$, $$$[4,2,3,1]$$$, $$$[4,3,1,2]$$$. The first six of them satisfy $$$f(p)=2$$$, while others satisfy $$$f(p)=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
Petya and Vasya are brothers. Today is a special day for them as their parents left them home alone and commissioned them to do n chores. Each chore is characterized by a single parameter — its complexity. The complexity of the i-th chore equals hi.

As Petya is older, he wants to take the chores with complexity larger than some value x (hi > x) to leave to Vasya the chores with complexity less than or equal to x (hi ≤ x). The brothers have already decided that Petya will do exactly a chores and Vasya will do exactly b chores (a + b = n).

In how many ways can they choose an integer x so that Petya got exactly a chores and Vasya got exactly b chores?

## Input Format
The first input line contains three integers n, a and b (2 ≤ n ≤ 2000; a, b ≥ 1; a + b = n) — the total number of chores, the number of Petya's chores and the number of Vasya's chores.

The next line contains a sequence of integers h1, h2, ..., hn (1 ≤ hi ≤ 109), hi is the complexity of the i-th chore. The numbers in the given sequence are not necessarily different.

All numbers on the lines are separated by single spaces.

## Output Format
Print the required number of ways to choose an integer value of x. If there are no such ways, print 0.

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

## Note
In the first sample the possible values of x are 3, 4 or 5.

In the second sample it is impossible to find such x, that Petya got 3 chores and Vasya got 4.

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 an integer a that consists of n digits. You are also given a sequence of digits s of length m. The digit in position j (1 ≤ j ≤ m) of sequence s means that you can choose an arbitrary position i (1 ≤ i ≤ n) in a and replace the digit in the chosen position i with sj. Each element in the sequence s can participate in no more than one replacing operation.

Your task is to perform such sequence of replacements, that the given number a gets maximum value. You are allowed to use not all elements from s.

## Input Format
The first line contains positive integer a. Its length n is positive and doesn't exceed 105. The second line contains sequence of digits s. Its length m is positive and doesn't exceed 105. The digits in the sequence s are written consecutively without any separators.

The given number a doesn't contain leading zeroes.

## Output Format
Print the maximum value that can be obtained from a after a series of replacements. You are allowed to use not all elements from s. The printed number shouldn't contain any leading zeroes.

## Examples
```input
1024
010
```
```output
1124
```
-----
```input
987
1234567
```
```output
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 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
Yeri has an array of $$$n + 2$$$ non-negative integers : $$$a_0, a_1, ..., a_n, a_{n + 1}$$$.

We know that $$$a_0 = a_{n + 1} = 0$$$.

She wants to make all the elements of $$$a$$$ equal to zero in the minimum number of operations.

In one operation she can do one of the following:

- Choose the leftmost maximum element and change it to the maximum of the elements on its left.
- Choose the rightmost maximum element and change it to the maximum of the elements on its right.

Help her find the minimum number of operations needed to make all elements of $$$a$$$ equal to zero.

## Input Format
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, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$).

## Output Format
Print a single integer  — the minimum number of operations needed to make all elements of $$$a$$$ equal to zero.

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

## Note
In the first sample, you get $$$\langle 1, \underline{1}, 2, 4, 0, 2 \rangle$$$ by performing the first operation and $$$\langle 1, 4, 2, \underline{2}, 0, 2 \rangle$$$ by performing the second operation.

One way to achieve our goal is shown below. (The underlines show the last change.) $$$\langle 1, 4, 2, 4, 0, 2 \rangle \to \langle 1, 4, 2, \underline{2}, 0, 2 \rangle \to \langle 1, \underline{1}, 2, 2, 0, 2 \rangle \to \langle 1, 1, 2, 2, 0, \underline{0} \rangle \to \langle 1, 1, 2, \underline{0}, 0, 0 \rangle \to \langle 1, 1, \underline{0}, 0, 0, 0 \rangle \to \langle \underline{0}, 1, 0, 0, 0, 0 \rangle \to \langle 0, \underline{0}, 0, 0, 0, 0 \rangle $$$

In the third sample each element is already equal to zero so no operations are needed.

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 a binary string $$$S$$$ of length $$$n$$$ indexed from $$$1$$$ to $$$n$$$. You can perform the following operation any number of times (possibly zero):

- Choose two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$). Let $$$cnt_0$$$ be the number of times 0 occurs in $$$S[l \ldots r]$$$ and $$$cnt_1$$$ be the number of times 1 occurs in $$$S[l \ldots r]$$$. You can pay $$$|cnt_0 - cnt_1| + 1$$$ coins and sort the $$$S[l \ldots r]$$$. (by $$$S[l \ldots r]$$$ we mean the substring of $$$S$$$ starting at position $$$l$$$ and ending at position $$$r$$$)For example if $$$S = $$$ 11001, we can perform the operation on $$$S[2 \ldots 4]$$$, paying $$$|2 - 1| + 1 = 2$$$ coins, and obtain $$$S = $$$ 10011 as a new string.

Find the minimum total number of coins required to sort $$$S$$$ in increasing order.

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

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

The second line of each test case contains a binary string $$$S$$$ of $$$n$$$ characters $$$S_1S_2 \ldots S_n$$$. ($$$S_i = $$$ 0 or $$$S_i = $$$ 1 for each $$$1 \le i \le n$$$)

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

## Output Format
For each test case, output the minimum total number of coins required to sort $$$S$$$ in increasing order.

## Examples
```input
7
1
1
2
10
3
101
4
1000
5
11010
6
110000
20
01000010001010011000
```
```output
0
1
1
3
2
2
5
```

## Note
In the first test case, $$$S$$$ is already sorted.

In the second test case, it's enough to apply the operation with $$$l = 1, r = 2$$$.

In the third test case, it's enough to apply the operation with $$$l = 1, r = 2$$$.

Now solve the problem and return the code.