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

# Problem
Omkar and Akmar are playing a game on a circular board with $$$n$$$ ($$$2 \leq n \leq 10^6$$$) cells. The cells are numbered from $$$1$$$ to $$$n$$$ so that for each $$$i$$$ ($$$1 \leq i \leq n-1$$$) cell $$$i$$$ is adjacent to cell $$$i+1$$$ and cell $$$1$$$ is adjacent to cell $$$n$$$. Initially, each cell is empty.

Omkar and Akmar take turns placing either an A or a B on the board, with Akmar going first. The letter must be placed on an empty cell. In addition, the letter cannot be placed adjacent to a cell containing the same letter.

A player loses when it is their turn and there are no more valid moves.

Output the number of possible distinct games where both players play optimally modulo $$$10^9+7$$$. Note that we only consider games where some player has lost and there are no more valid moves.

Two games are considered distinct if the number of turns is different or for some turn, the letter or cell number that the letter is placed on were different.

A move is considered optimal if the move maximizes the player's chance of winning, assuming the other player plays optimally as well. More formally, if the player who has to move has a winning strategy, they have to make a move after which they will still have a winning strategy. If they do not, they can make any move.

## Input Format
The only line will contain an integer $$$n$$$ ($$$2 \leq n \leq 10^6$$$) — the number of cells on the board.

## Output Format
Output a single integer — the number of possible distinct games where both players play optimally modulo $$$10^9+7$$$.

## Examples
```input
2
```
```output
4
```
-----
```input
69420
```
```output
629909355
```
-----
```input
42069
```
```output
675837193
```

## Note
For the first sample case, the first player has $$$4$$$ possible moves. No matter what the first player plays, the second player only has $$$1$$$ possible move, so there are $$$4$$$ possible games.

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: 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 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
Vasya adores sport programming. He can't write programs but he loves to watch the contests' progress. Vasya even has a favorite coder and Vasya pays special attention to him.

One day Vasya decided to collect the results of all contests where his favorite coder participated and track the progress of his coolness. For each contest where this coder participated, he wrote out a single non-negative number — the number of points his favorite coder earned in the contest. Vasya wrote out the points for the contest in the order, in which the contests run (naturally, no two contests ran simultaneously).

Vasya considers a coder's performance in a contest amazing in two situations: he can break either his best or his worst performance record. First, it is amazing if during the contest the coder earns strictly more points that he earned on each past contest. Second, it is amazing if during the contest the coder earns strictly less points that he earned on each past contest. A coder's first contest isn't considered amazing. Now he wants to count the number of amazing performances the coder had throughout his whole history of participating in contests. But the list of earned points turned out long and Vasya can't code... That's why he asks you to help him.

## Input Format
The first line contains the single integer n (1 ≤ n ≤ 1000) — the number of contests where the coder participated.

The next line contains n space-separated non-negative integer numbers — they are the points which the coder has earned. The points are given in the chronological order. All points do not exceed 10000.

## Output Format
Print the single number — the number of amazing performances the coder has had during his whole history of participating in the contests.

## Examples
```input
5
100 50 200 150 200
```
```output
2
```
-----
```input
10
4664 6496 5814 7010 5762 5736 6944 4850 3698 7242
```
```output
4
```

## Note
In the first sample the performances number 2 and 3 are amazing.

In the second sample the performances number 2, 4, 9 and 10 are amazing.

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
Ilya plays a card game by the following rules.

A player has several cards. Each card contains two non-negative integers inscribed, one at the top of the card and one at the bottom. At the beginning of the round the player chooses one of his cards to play it. If the top of the card contains number ai, and the bottom contains number bi, then when the player is playing the card, he gets ai points and also gets the opportunity to play additional bi cards. After the playing the card is discarded.

More formally: let's say that there is a counter of the cards that can be played. At the beginning of the round the counter equals one. When a card is played, the counter decreases by one for the played card and increases by the number bi, which is written at the bottom of the card. Then the played card is discarded. If after that the counter is not equal to zero, the player gets the opportunity to play another card from the remaining cards. The round ends when the counter reaches zero or the player runs out of cards.

Of course, Ilya wants to get as many points as possible. Can you determine the maximum number of points he can score provided that you know his cards?

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of cards Ilya has.

Each of the next n lines contains two non-negative space-separated integers — ai and bi (0 ≤ ai, bi ≤ 104) — the numbers, written at the top and the bottom of the i-th card correspondingly.

## Output Format
Print the single number — the maximum number of points you can score in one round by the described rules.

## Examples
```input
2
1 0
2 0
```
```output
2
```
-----
```input
3
1 0
2 0
0 2
```
```output
3
```

## Note
In the first sample none of two cards brings extra moves, so you should play the one that will bring more points.

In the second sample you should first play the third card that doesn't bring any points but lets you play both remaining cards.

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
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 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 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 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
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 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
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 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
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.