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
To satisfy his love of matching socks, Phoenix has brought his $$$n$$$ socks ($$$n$$$ is even) to the sock store. Each of his socks has a color $$$c_i$$$ and is either a left sock or right sock.

Phoenix can pay one dollar to the sock store to either:

- recolor a sock to any color $$$c'$$$ $$$(1 \le c' \le n)$$$
- turn a left sock into a right sock
- turn a right sock into a left sock

The sock store may perform each of these changes any number of times. Note that the color of a left sock doesn't change when it turns into a right sock, and vice versa.

A matching pair of socks is a left and right sock with the same color. What is the minimum cost for Phoenix to make $$$n/2$$$ matching pairs? Each sock must be included in exactly one matching pair.

## Input Format
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$l$$$, and $$$r$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$n$$$ is even; $$$0 \le l, r \le n$$$; $$$l+r=n$$$) — the total number of socks, and the number of left and right socks, respectively.

The next line contains $$$n$$$ integers $$$c_i$$$ ($$$1 \le c_i \le n$$$) — the colors of the socks. The first $$$l$$$ socks are left socks, while the next $$$r$$$ socks are right socks.

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

## Output Format
For each test case, print one integer — the minimum cost for Phoenix to make $$$n/2$$$ matching pairs. Each sock must be included in exactly one matching pair.

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

## Note
In the first test case, Phoenix can pay $$$2$$$ dollars to:

- recolor sock $$$1$$$ to color $$$2$$$
- recolor sock $$$3$$$ to color $$$2$$$

In the second test case, Phoenix can pay $$$3$$$ dollars to:

- turn sock $$$6$$$ from a right sock to a left sock
- recolor sock $$$3$$$ to color $$$1$$$
- recolor sock $$$4$$$ to color $$$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: 4.0 seconds
Memory limit: 256.0 MB

# Problem
Two painters, Amin and Benj, are repainting Gregor's living room ceiling! The ceiling can be modeled as an $$$n \times m$$$ grid.

For each $$$i$$$ between $$$1$$$ and $$$n$$$, inclusive, painter Amin applies $$$a_i$$$ layers of paint to the entire $$$i$$$-th row. For each $$$j$$$ between $$$1$$$ and $$$m$$$, inclusive, painter Benj applies $$$b_j$$$ layers of paint to the entire $$$j$$$-th column. Therefore, the cell $$$(i,j)$$$ ends up with $$$a_i+b_j$$$ layers of paint.

Gregor considers the cell $$$(i,j)$$$ to be badly painted if $$$a_i+b_j \le x$$$. Define a badly painted region to be a maximal connected component of badly painted cells, i. e. a connected component of badly painted cells such that all adjacent to the component cells are not badly painted. Two cells are considered adjacent if they share a side.

Gregor is appalled by the state of the finished ceiling, and wants to know the number of badly painted regions.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$ and $$$x$$$ ($$$1 \le n,m \le 2\cdot 10^5$$$, $$$1 \le x \le 2\cdot 10^5$$$) — the dimensions of Gregor's ceiling, and the maximum number of paint layers in a badly painted cell.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2\cdot 10^5$$$), the number of paint layers Amin applies to each row.

The third line contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \le b_j \le 2\cdot 10^5$$$), the number of paint layers Benj applies to each column.

## Output Format
Print a single integer, the number of badly painted regions.

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

## Note
The diagram below represents the first example. The numbers to the left of each row represent the list $$$a$$$, and the numbers above each column represent the list $$$b$$$. The numbers inside each cell represent the number of paint layers in that cell.

The colored cells correspond to badly painted cells. The red and blue cells respectively form $$$2$$$ badly painted regions.

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 an array $$$a$$$ consisting of $$$n$$$ positive (greater than $$$0$$$) integers beautiful if the following condition is held for every $$$i$$$ from $$$1$$$ to $$$n$$$: either $$$a_i = 1$$$, or at least one of the numbers $$$a_i - 1$$$ and $$$a_i - 2$$$ exists in the array as well.

For example:

- the array $$$[5, 3, 1]$$$ is beautiful: for $$$a_1$$$, the number $$$a_1 - 2 = 3$$$ exists in the array; for $$$a_2$$$, the number $$$a_2 - 2 = 1$$$ exists in the array; for $$$a_3$$$, the condition $$$a_3 = 1$$$ holds;
- the array $$$[1, 2, 2, 2, 2]$$$ is beautiful: for $$$a_1$$$, the condition $$$a_1 = 1$$$ holds; for every other number $$$a_i$$$, the number $$$a_i - 1 = 1$$$ exists in the array;
- the array $$$[1, 4]$$$ is not beautiful: for $$$a_2$$$, neither $$$a_2 - 2 = 2$$$ nor $$$a_2 - 1 = 3$$$ exists in the array, and $$$a_2 \ne 1$$$;
- the array $$$[2]$$$ is not beautiful: for $$$a_1$$$, neither $$$a_1 - 1 = 1$$$ nor $$$a_1 - 2 = 0$$$ exists in the array, and $$$a_1 \ne 1$$$;
- the array $$$[2, 1, 3]$$$ is beautiful: for $$$a_1$$$, the number $$$a_1 - 1 = 1$$$ exists in the array; for $$$a_2$$$, the condition $$$a_2 = 1$$$ holds; for $$$a_3$$$, the number $$$a_3 - 2 = 1$$$ exists in the array.

You are given a positive integer $$$s$$$. Find the minimum possible size of a beautiful array with the sum of elements equal to $$$s$$$.

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

Then $$$t$$$ lines follow, the $$$i$$$-th line contains one integer $$$s$$$ ($$$1 \le s \le 5000$$$) for the $$$i$$$-th test case.

## Output Format
Print $$$t$$$ integers, the $$$i$$$-th integer should be the answer for the $$$i$$$-th testcase: the minimum possible size of a beautiful array with the sum of elements equal to $$$s$$$.

## Examples
```input
4
1
8
7
42
```
```output
1
3
3
7
```

## Note
Consider the example test:

1. in the first test case, the array $$$[1]$$$ meets all conditions;
2. in the second test case, the array $$$[3, 4, 1]$$$ meets all conditions;
3. in the third test case, the array $$$[1, 2, 4]$$$ meets all conditions;
4. in the fourth test case, the array $$$[1, 4, 6, 8, 10, 2, 11]$$$ meets all conditions.

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 string $$$s$$$ of length $$$n$$$ consisting only of the characters 0 and 1.

You perform the following operation until the string becomes empty: choose some consecutive substring of equal characters, erase it from the string and glue the remaining two parts together (any of them can be empty) in the same order. For example, if you erase the substring 111 from the string 111110, you will get the string 110. When you delete a substring of length $$$l$$$, you get $$$a \cdot l + b$$$ points.

Your task is to calculate the maximum number of points that you can score in total, if you have to make the given string empty.

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

The first line of each testcase contains three integers $$$n$$$, $$$a$$$ and $$$b$$$ ($$$1 \le n \le 100; -100 \le a, b \le 100$$$) — the length of the string $$$s$$$ and the parameters $$$a$$$ and $$$b$$$.

The second line contains the string $$$s$$$. The string $$$s$$$ consists only of the characters 0 and 1.

## Output Format
For each testcase, print a single integer — the maximum number of points that you can score.

## Examples
```input
3
3 2 0
000
5 -2 5
11001
6 1 -4
100111
```
```output
6
15
-2
```

## Note
In the first example, it is enough to delete the entire string, then we will get $$$2 \cdot 3 + 0 = 6$$$ points.

In the second example, if we delete characters one by one, then for each deleted character we will get $$$(-2) \cdot 1 + 5 = 3$$$ points, i. e. $$$15$$$ points in total.

In the third example, we can delete the substring 00 from the string 100111, we get $$$1 \cdot 2 + (-4) = -2$$$ points, and the string will be equal to 1111, removing it entirely we get $$$1 \cdot 4 + (-4) = 0$$$ points. In total, we got $$$-2$$$ points for $$$2$$$ operations.

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
Suppose you have two points $$$p = (x_p, y_p)$$$ and $$$q = (x_q, y_q)$$$. Let's denote the Manhattan distance between them as $$$d(p, q) = |x_p - x_q| + |y_p - y_q|$$$.

Let's say that three points $$$p$$$, $$$q$$$, $$$r$$$ form a bad triple if $$$d(p, r) = d(p, q) + d(q, r)$$$.

Let's say that an array $$$b_1, b_2, \dots, b_m$$$ is good if it is impossible to choose three distinct indices $$$i$$$, $$$j$$$, $$$k$$$ such that the points $$$(b_i, i)$$$, $$$(b_j, j)$$$ and $$$(b_k, k)$$$ form a bad triple.

You are given an array $$$a_1, a_2, \dots, a_n$$$. Calculate the number of good subarrays of $$$a$$$. A subarray of the array $$$a$$$ is the array $$$a_l, a_{l + 1}, \dots, a_r$$$ for some $$$1 \le l \le r \le n$$$.

Note that, according to the definition, subarrays of length $$$1$$$ and $$$2$$$ are good.

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

The first line of each test case contains one integer $$$n$$$ ($$$1 \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, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

## Output Format
For each test case, print the number of good subarrays of array $$$a$$$.

## Examples
```input
3
4
2 4 1 3
5
6 9 1 9 6
2
13 37
```
```output
10
12
3
```

## Note
In the first test case, it can be proven that any subarray of $$$a$$$ is good. For example, subarray $$$[a_2, a_3, a_4]$$$ is good since it contains only three elements and:

- $$$d((a_2, 2), (a_4, 4)) = |4 - 3| + |2 - 4| = 3$$$ $$$<$$$ $$$d((a_2, 2), (a_3, 3)) + d((a_3, 3), (a_4, 4)) = 3 + 1 + 2 + 1 = 7$$$;
- $$$d((a_2, 2), (a_3, 3))$$$ $$$<$$$ $$$d((a_2, 2), (a_4, 4)) + d((a_4, 4), (a_3, 3))$$$;
- $$$d((a_3, 3), (a_4, 4))$$$ $$$<$$$ $$$d((a_3, 3), (a_2, 2)) + d((a_2, 2), (a_4, 4))$$$;

In the second test case, for example, subarray $$$[a_1, a_2, a_3, a_4]$$$ is not good, since it contains a bad triple $$$(a_1, 1)$$$, $$$(a_2, 2)$$$, $$$(a_4, 4)$$$:

- $$$d((a_1, 1), (a_4, 4)) = |6 - 9| + |1 - 4| = 6$$$;
- $$$d((a_1, 1), (a_2, 2)) = |6 - 9| + |1 - 2| = 4$$$;
- $$$d((a_2, 2), (a_4, 4)) = |9 - 9| + |2 - 4| = 2$$$;

So, $$$d((a_1, 1), (a_4, 4)) = d((a_1, 1), (a_2, 2)) + d((a_2, 2), (a_4, 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 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
Let's call an integer array $$$a_1, a_2, \dots, a_n$$$ good if $$$a_i \neq i$$$ for each $$$i$$$.

Let $$$F(a)$$$ be the number of pairs $$$(i, j)$$$ ($$$1 \le i < j \le n$$$) such that $$$a_i + a_j = i + j$$$.

Let's say that an array $$$a_1, a_2, \dots, a_n$$$ is excellent if:

- $$$a$$$ is good;
- $$$l \le a_i \le r$$$ for each $$$i$$$;
- $$$F(a)$$$ is the maximum possible among all good arrays of size $$$n$$$.

Given $$$n$$$, $$$l$$$ and $$$r$$$, calculate the number of excellent arrays modulo $$$10^9 + 7$$$.

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

The first and only line of each test case contains three integers $$$n$$$, $$$l$$$, and $$$r$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$-10^9 \le l \le 1$$$; $$$n \le r \le 10^9$$$).

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

## Output Format
For each test case, print the number of excellent arrays modulo $$$10^9 + 7$$$.

## Examples
```input
4
3 0 3
4 -3 5
42 -33 55
69 -42 146
```
```output
4
10
143922563
698570404
```

## Note
In the first test case, it can be proven that the maximum $$$F(a)$$$ among all good arrays $$$a$$$ is equal to $$$2$$$. The excellent arrays are:

1. $$$[2, 1, 2]$$$;
2. $$$[0, 3, 2]$$$;
3. $$$[2, 3, 2]$$$;
4. $$$[3, 0, 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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a string $$$s$$$ of length $$$n$$$. Each character is either one of the first $$$k$$$ lowercase Latin letters or a question mark.

You are asked to replace every question mark with one of the first $$$k$$$ lowercase Latin letters in such a way that the following value is maximized.

Let $$$f_i$$$ be the maximum length substring of string $$$s$$$, which consists entirely of the $$$i$$$-th Latin letter. A substring of a string is a contiguous subsequence of that string. If the $$$i$$$-th letter doesn't appear in a string, then $$$f_i$$$ is equal to $$$0$$$.

The value of a string $$$s$$$ is the minimum value among $$$f_i$$$ for all $$$i$$$ from $$$1$$$ to $$$k$$$.

What is the maximum value the string can have?

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 17$$$) — the length of the string and the number of first Latin letters used.

The second line contains a string $$$s$$$, consisting of $$$n$$$ characters. Each character is either one of the first $$$k$$$ lowercase Latin letters or a question mark.

## Output Format
Print a single integer — the maximum value of the string after every question mark is replaced with one of the first $$$k$$$ lowercase Latin letters.

## Examples
```input
10 2
a??ab????b
```
```output
4
```
-----
```input
9 4
?????????
```
```output
2
```
-----
```input
2 3
??
```
```output
0
```
-----
```input
15 3
??b?babbc??b?aa
```
```output
3
```
-----
```input
4 4
cabd
```
```output
1
```

## Note
In the first example the question marks can be replaced in the following way: "aaaababbbb". $$$f_1 = 4$$$, $$$f_2 = 4$$$, thus the answer is $$$4$$$. Replacing it like this is also possible: "aaaabbbbbb". That way $$$f_1 = 4$$$, $$$f_2 = 6$$$, however, the minimum of them is still $$$4$$$.

In the second example one of the possible strings is "aabbccdda".

In the third example at least one letter won't appear in the string, thus, the minimum of values $$$f_i$$$ is always $$$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: 512.0 MB

# Problem
You have a permutation: an array $$$a = [a_1, a_2, \ldots, a_n]$$$ of distinct integers from $$$1$$$ to $$$n$$$. The length of the permutation $$$n$$$ is odd.

Consider the following algorithm of sorting the permutation in increasing order.

A helper procedure of the algorithm, $$$f(i)$$$, takes a single argument $$$i$$$ ($$$1 \le i \le n-1$$$) and does the following. If $$$a_i > a_{i+1}$$$, the values of $$$a_i$$$ and $$$a_{i+1}$$$ are exchanged. Otherwise, the permutation doesn't change.

The algorithm consists of iterations, numbered with consecutive integers starting with $$$1$$$. On the $$$i$$$-th iteration, the algorithm does the following:

- if $$$i$$$ is odd, call $$$f(1), f(3), \ldots, f(n - 2)$$$;
- if $$$i$$$ is even, call $$$f(2), f(4), \ldots, f(n - 1)$$$.

It can be proven that after a finite number of iterations the permutation will be sorted in increasing order.

After how many iterations will this happen for the first time?

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 999$$$; $$$n$$$ is odd) — the length of the permutation.

The second line contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the permutation itself.

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

## Output Format
For each test case print the number of iterations after which the permutation will become sorted in increasing order for the first time.

If the given permutation is already sorted, print $$$0$$$.

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

## Note
In the first test case, the permutation will be changing as follows:

- after the $$$1$$$-st iteration: $$$[2, 3, 1]$$$;
- after the $$$2$$$-nd iteration: $$$[2, 1, 3]$$$;
- after the $$$3$$$-rd iteration: $$$[1, 2, 3]$$$.

In the second test case, the permutation will be changing as follows:

- after the $$$1$$$-st iteration: $$$[4, 5, 1, 7, 2, 3, 6]$$$;
- after the $$$2$$$-nd iteration: $$$[4, 1, 5, 2, 7, 3, 6]$$$;
- after the $$$3$$$-rd iteration: $$$[1, 4, 2, 5, 3, 7, 6]$$$;
- after the $$$4$$$-th iteration: $$$[1, 2, 4, 3, 5, 6, 7]$$$;
- after the $$$5$$$-th iteration: $$$[1, 2, 3, 4, 5, 6, 7]$$$.

In the third test case, the permutation is already sorted and the answer is $$$0$$$.

Now solve the problem and return the code.