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

# Problem
Vasya lives in a strange world. The year has n months and the i-th month has ai days. Vasya got a New Year present — the clock that shows not only the time, but also the date.

The clock's face can display any number from 1 to d. It is guaranteed that ai ≤ d for all i from 1 to n. The clock does not keep information about the current month, so when a new day comes, it simply increases the current day number by one. The clock cannot display number d + 1, so after day number d it shows day 1 (the current day counter resets). The mechanism of the clock allows you to increase the day number by one manually. When you execute this operation, day d is also followed by day 1.

Vasya begins each day checking the day number on the clock. If the day number on the clock does not match the actual day number in the current month, then Vasya manually increases it by one. Vasya is persistent and repeats this operation until the day number on the clock matches the actual number of the current day in the current month.

A year passed and Vasya wonders how many times he manually increased the day number by one, from the first day of the first month to the last day of the n-th month inclusive, considering that on the first day of the first month the clock display showed day 1.

## Input Format
The first line contains the single number d — the maximum number of the day that Vasya's clock can show (1 ≤ d ≤ 106).

The second line contains a single integer n — the number of months in the year (1 ≤ n ≤ 2000).

The third line contains n space-separated integers: ai (1 ≤ ai ≤ d) — the number of days in each month in the order in which they follow, starting from the first one.

## Output Format
Print a single number — the number of times Vasya manually increased the day number by one throughout the last year.

## Examples
```input
4
2
2 2
```
```output
2
```
-----
```input
5
3
3 4 3
```
```output
3
```
-----
```input
31
12
31 28 31 30 31 30 31 31 30 31 30 31
```
```output
7
```

## Note
In the first sample the situation is like this:

- Day 1. Month 1. The clock shows 1. Vasya changes nothing.
- Day 2. Month 1. The clock shows 2. Vasya changes nothing.
- Day 1. Month 2. The clock shows 3. Vasya manually increases the day number by 1. After that the clock shows 4. Vasya increases the day number by 1 manually. After that the clock shows 1.
- Day 2. Month 2. The clock shows 2. Vasya changes nothing.

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
And here goes another problem on arrays. You are given positive integer len and array a which consists of n integers a1, a2, ..., an. Let's introduce two characteristics for the given array.

- Let's consider an arbitrary interval of the array with length len, starting in position i. Value $$\text{modSum}(i, \text{len}) = \left| \sum_{j=i}^{i+\text{len}-1} a_j \right|$$, is the modular sum on the chosen interval. In other words, the modular sum is the sum of integers on the chosen interval with length len, taken in its absolute value.
- Value $$\max_{1 \leq i \leq n - len + 1} modSum(i, len)$$ is the optimal sum of the array. In other words, the optimal sum of an array is the maximum of all modular sums on various intervals of array with length len.

Your task is to calculate the optimal sum of the given array a. However, before you do the calculations, you are allowed to produce no more than k consecutive operations of the following form with this array: one operation means taking an arbitrary number from array ai and multiply it by -1. In other words, no more than k times you are allowed to take an arbitrary number ai from the array and replace it with  - ai. Each number of the array is allowed to choose an arbitrary number of times.

Your task is to calculate the maximum possible optimal sum of the array after at most k operations described above are completed.

## Input Format
The first line contains two integers n, len (1 ≤ len ≤ n ≤ 105) — the number of elements in the array and the length of the chosen subinterval of the array, correspondingly.

The second line contains a sequence consisting of n integers a1, a2, ..., an (|ai| ≤ 109) — the original array.

The third line contains a single integer k (0 ≤ k ≤ n) — the maximum allowed number of operations.

All numbers in lines are separated by a single space.

## Output Format
In a single line print the maximum possible optimal sum after no more than k acceptable operations are fulfilled.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

## Examples
```input
5 3
0 -2 3 -5 1
2
```
```output
10
```
-----
```input
5 2
1 -3 -10 4 1
3
```
```output
14
```
-----
```input
3 3
-2 -5 4
1
```
```output
11
```

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
An integer template is a string consisting of digits and/or question marks.

A positive (strictly greater than $$$0$$$) integer matches the integer template if it is possible to replace every question mark in the template with a digit in such a way that we get the decimal representation of that integer without any leading zeroes.

For example:

- $$$42$$$ matches 4?;
- $$$1337$$$ matches ????;
- $$$1337$$$ matches 1?3?;
- $$$1337$$$ matches 1337;
- $$$3$$$ does not match ??;
- $$$8$$$ does not match ???8;
- $$$1337$$$ does not match 1?7.

You are given an integer template consisting of at most $$$5$$$ characters. Calculate the number of positive (strictly greater than $$$0$$$) integers that match it.

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

Each test case consists of one line containing the string $$$s$$$ ($$$1 \le |s| \le 5$$$) consisting of digits and/or question marks — the integer template for the corresponding test case.

## Output Format
For each test case, print one integer — the number of positive (strictly greater than $$$0$$$) integers that match the template.

## Examples
```input
8
??
?
0
9
03
1??7
?5?
9??99
```
```output
90
9
0
1
0
100
90
100
```

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$$$, consisting of lowercase Latin letters.

In one operation, you can select several (one or more) positions in it such that no two selected positions are adjacent to each other. Then you remove the letters on the selected positions from the string. The resulting parts are concatenated without changing their order.

What is the smallest number of operations required to make all the letters in $$$s$$$ the same?

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

The only line of each testcase contains a string $$$s$$$, consisting of lowercase Latin letters. Its length is from $$$1$$$ to $$$2 \cdot 10^5$$$.

The total length of the strings over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each testcase, print a single integer — the smallest number of operations required to make all the letters in the given string $$$s$$$ the same.

## Examples
```input
5
abacaba
codeforces
oooooooo
abcdef
mewheniseearulhiiarul
```
```output
1
3
0
2
4
```

## Note
In the first testcase, you can select positions $$$2, 4$$$ and $$$6$$$ and remove the corresponding letters 'b', 'c' and 'b'.

In the third testcase, the letters in the string are already the same, so you don't have to make any operations.

In the fourth testcase, one of the possible solutions in $$$2$$$ operations is the following. You can select positions $$$1, 4, 6$$$ first. The string becomes "bce". Then select positions $$$1$$$ and $$$3$$$. The string becomes "c". All letters in it are the same, since it's just one letter.

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.

You are given a regular bracket sequence. In one move, you can remove a pair of adjacent brackets such that the left one is an opening bracket and the right one is a closing bracket. Then concatenate the resulting parts without changing the order. The cost of this move is the number of brackets to the right of the right bracket of this pair.

The cost of the regular bracket sequence is the smallest total cost of the moves required to make the sequence empty.

Actually, you are not removing any brackets. Instead, you are given a regular bracket sequence and an integer $$$k$$$. You can perform the following operation at most $$$k$$$ times:

- extract some bracket from the sequence and insert it back at any position (between any two brackets, at the start or at the end; possibly, at the same place it was before).

After all operations are performed, the bracket sequence has to be regular. What is the smallest possible cost of the resulting regular bracket sequence?

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

The first line of each testcase contains a single integer $$$k$$$ ($$$0 \le k \le 5$$$) — the maximum number of operations you can perform.

The second line contains a non-empty regular bracket sequence, it consists only of characters '(' and ')'.

The total length of the regular bracket sequences over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each testcase, print a single integer — the smallest possible cost of the regular bracket sequence after you perform at most $$$k$$$ operations on it.

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

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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
There is a beautiful alley with trees in front of a shopping mall. Unfortunately, it has to go to make space for the parking lot.

The trees on the alley all grow in a single line. There are $$$n$$$ spots for trees, index $$$0$$$ is the shopping mall, index $$$n+1$$$ is the road and indices from $$$1$$$ to $$$n$$$ are the spots for trees. Some of them are taken — there grow trees of the same height $$$k$$$. No more than one tree grows in each spot.

When you chop down a tree in the spot $$$x$$$, you can make it fall either left or right. If it falls to the left, it takes up spots from $$$x-k$$$ to $$$x$$$, inclusive. If it falls to the right, it takes up spots from $$$x$$$ to $$$x+k$$$, inclusive.

Let $$$m$$$ trees on the alley grow in some spots $$$x_1, x_2, \dots, x_m$$$. Let an alley be called unfortunate if all $$$m$$$ trees can be chopped down in such a way that:

- no tree falls on the shopping mall or the road;
- each spot is taken up by no more than one fallen tree.

Calculate the number of different unfortunate alleys with $$$m$$$ trees of height $$$k$$$. Two alleys are considered different if there is a spot $$$y$$$ such that a tree grows in $$$y$$$ on the first alley and doesn't grow in $$$y$$$ on the second alley.

Output the number modulo $$$998\,244\,353$$$.

## Input Format
The only line contains three integers $$$n, m$$$ and $$$k$$$ ($$$1 \le m, k \le n \le 3 \cdot 10^5$$$) — the number of spots for the trees, the number of trees and the height of each tree.

## Output Format
Print a single integer — the number of different unfortunate alleys with $$$m$$$ trees of height $$$k$$$, modulo $$$998\,244\,353$$$.

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

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
LuoTianyi gives you a palindrome$$$^{\dagger}$$$ string $$$s$$$, and she wants you to find out the length of the longest non-empty subsequence$$$^{\ddagger}$$$ of $$$s$$$ which is not a palindrome string. If there is no such subsequence, output $$$-1$$$ instead.

$$$^{\dagger}$$$ A palindrome is a string that reads the same backward as forward. For example, strings "z", "aaa", "aba", "abccba" are palindromes, but strings "codeforces", "reality", "ab" are not.

$$$^{\ddagger}$$$ A string $$$a$$$ is a subsequence of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from $$$b$$$. For example, strings "a", "aaa", "bab" are subsequences of string "abaab", but strings "codeforces", "bbb", "h" are not.

## Input Format
Each test consists of multiple test cases. 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 and the only line of each test case contains a single string $$$s$$$ ($$$1 \le |s| \le 50$$$) consisting of lowercase English letters — the string that LuoTianyi gives you. It's guaranteed that $$$s$$$ is a palindrome string.

## Output Format
For each test case, output a single integer — the length of the longest non-empty subsequence which is not a palindrome string. If there is no such subsequence, output $$$-1$$$.

## Examples
```input
4
abacaba
aaa
codeforcesecrofedoc
lol
```
```output
6
-1
18
2
```

## Note
In the first test case, "abcaba" is a subsequence of "abacaba" as we can delete the third letter of "abacaba" to get "abcaba", and "abcaba" is not a palindrome string. We can prove that "abcaba" is an example of the longest subsequences of "abacaba" that isn't palindrome, so that the answer is $$$6$$$.

In the second test case, we can only get "a" and "aa", but they are all palindrome strings, so the answer is $$$-1$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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
Sasha found an array $$$a$$$ consisting of $$$n$$$ integers and asked you to paint elements.

You have to paint each element of the array. You can use as many colors as you want, but each element should be painted into exactly one color, and for each color, there should be at least one element of that color.

The cost of one color is the value of $$$\max(S) - \min(S)$$$, where $$$S$$$ is the sequence of elements of that color. The cost of the whole coloring is the sum of costs over all colors.

For example, suppose you have an array $$$a = [\color{red}{1}, \color{red}{5}, \color{blue}{6}, \color{blue}{3}, \color{red}{4}]$$$, and you painted its elements into two colors as follows: elements on positions $$$1$$$, $$$2$$$ and $$$5$$$ have color $$$1$$$; elements on positions $$$3$$$ and $$$4$$$ have color $$$2$$$. Then:

- the cost of the color $$$1$$$ is $$$\max([1, 5, 4]) - \min([1, 5, 4]) = 5 - 1 = 4$$$;
- the cost of the color $$$2$$$ is $$$\max([6, 3]) - \min([6, 3]) = 6 - 3 = 3$$$;
- the total cost of the coloring is $$$7$$$.

For the given array $$$a$$$, you have to calculate the maximum possible cost of the coloring.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 50$$$) — length of $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 50$$$) — array $$$a$$$.

## Output Format
For each test case output the maximum possible cost of the coloring.

## Examples
```input
6
5
1 5 6 3 4
1
5
4
1 6 3 9
6
1 13 9 3 7 2
4
2 2 2 2
5
4 5 2 2 3
```
```output
7
0
11
23
0
5
```

## Note
In the first example one of the optimal coloring is $$$[\color{red}{1}, \color{red}{5}, \color{blue}{6}, \color{blue}{3}, \color{red}{4}]$$$. The answer is $$$(5 - 1) + (6 - 3) = 7$$$.

In the second example, the only possible coloring is $$$[\color{blue}{5}]$$$, for which the answer is $$$5 - 5 = 0$$$.

In the third example, the optimal coloring is $$$[\color{blue}{1}, \color{red}{6}, \color{red}{3}, \color{blue}{9}]$$$, the answer is $$$(9 - 1) + (6 - 3) = 11$$$.

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
Today Alex was brought array $$$a_1, a_2, \dots, a_n$$$ of length $$$n$$$. He can apply as many operations as he wants (including zero operations) to change the array elements.

In $$$1$$$ operation Alex can choose any $$$l$$$ and $$$r$$$ such that $$$1 \leq l \leq r \leq n$$$, and multiply all elements of the array from $$$l$$$ to $$$r$$$ inclusive by $$$-1$$$. In other words, Alex can replace the subarray $$$[a_l, a_{l + 1}, \dots, a_r]$$$ by $$$[-a_l, -a_{l + 1}, \dots, -a_r]$$$ in $$$1$$$ operation.

For example, let $$$n = 5$$$, the array is $$$[1, -2, 0, 3, -1]$$$, $$$l = 2$$$ and $$$r = 4$$$, then after the operation the array will be $$$[1, 2, 0, -3, -1]$$$.

Alex is late for school, so you should help him find the maximum possible sum of numbers in the array, which can be obtained by making any number of operations, as well as the minimum number of operations that must be done for this.

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

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) — elements of the array.

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

## Output Format
For each test case output two space-separated numbers: the maximum possible sum of numbers in the array and the minimum number of operations to get this sum.

Pay attention that an answer may not fit in a standard integer type, so do not forget to use 64-bit integer type.

## Examples
```input
5
6
-1 7 -4 -2 5 -8
8
-1 0 0 -2 1 0 -3 0
5
2 -1 0 -3 -7
5
0 -17 0 1 0
4
-1 0 -2 -1
```
```output
27 3
7 2
13 1
18 1
4 1
```

## Note
Below, for each test case, only one of the possible shortest sequences of operations is provided among many. There are others that have the same length and lead to the maximum sum of elements.

In the first test case, Alex can make operations: $$$(1, 4)$$$, $$$(2, 2)$$$, $$$(6, 6)$$$.

In the second test case, to get the largest sum you need to make operations: $$$(1, 8)$$$, $$$(5, 6)$$$.

In the fourth test case, it is necessary to make only one operation: $$$(2, 3)$$$.

Now solve the problem and return the code.