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 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
Madoka has become too lazy to write a legend, so let's go straight to the formal description of the problem.

An array of integers $$$a_1, a_2, \ldots, a_n$$$ is called a hill if it is not empty and there is an index $$$i$$$ in it, for which the following is true: $$$a_1 < a_2 < \ldots < a_i > a_{i + 1} > a_{i + 2} > \ldots > a_n$$$.

A sequence $$$x$$$ is a subsequence of a sequence $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by deletion of several (possibly, zero or all) elements keeping the order of the other elements. For example, for an array $$$[69, 1000, 228, -7]$$$ the array $$$[1000, -7]$$$ is a subsequence, while $$$[1]$$$ and $$$[-7, 1000]$$$ are not.

Splitting an array into two subsequences is called good if each element belongs to exactly one subsequence, and also each of these subsequences is a hill.

You are given an array of distinct positive integers $$$a_1, a_2, \ldots a_n$$$. It is required to find the number of different pairs of maxima of the first and second subsequences among all good splits. Two pairs that only differ in the order of elements are considered same.

## Input Format
The first line of input contains a single integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — array size.

The second line of input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array. It is guaranteed that all $$$a_i$$$ are pairwise distinct.

## Output Format
In a single line, print exactly one number — the number of different pairs of maxima of the first and second subsequences among all good splits.

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

## Note
In the first test case there are 3 possible pairs: $$$(3, 4)$$$, $$$(2, 4)$$$, $$$(1, 4)$$$. And they are achieved with the following partitions: $$$[1, 2, 3], [4]$$$; $$$[4, 3], [1, 2]$$$; $$$[1], [2, 4, 3]$$$

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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
One day Vasya painted a Cartesian coordinate system on a piece of paper and marked some set of points (x1, y1), (x2, y2), ..., (xn, yn). Let's define neighbors for some fixed point from the given set (x, y):

- point (x', y') is (x, y)'s right neighbor, if x' > x and y' = y
- point (x', y') is (x, y)'s left neighbor, if x' < x and y' = y
- point (x', y') is (x, y)'s lower neighbor, if x' = x and y' < y
- point (x', y') is (x, y)'s upper neighbor, if x' = x and y' > y

We'll consider point (x, y) from the given set supercentral, if it has at least one upper, at least one lower, at least one left and at least one right neighbor among this set's points.

Vasya marked quite many points on the paper. Analyzing the picture manually is rather a challenge, so Vasya asked you to help him. Your task is to find the number of supercentral points in the given set.

## Input Format
The first input line contains the only integer n (1 ≤ n ≤ 200) — the number of points in the given set. Next n lines contain the coordinates of the points written as "x y" (without the quotes) (|x|, |y| ≤ 1000), all coordinates are integers. The numbers in the line are separated by exactly one space. It is guaranteed that all points are different.

## Output Format
Print the only number — the number of supercentral points of the given set.

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

## Note
In the first sample the supercentral points are only points (1, 1) and (1, 2).

In the second sample there is one supercental point — point (0, 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: 256.0 MB

# Problem
One day a highly important task was commissioned to Vasya — writing a program in a night. The program consists of n lines of code. Vasya is already exhausted, so he works like that: first he writes v lines of code, drinks a cup of tea, then he writes as much as $$\left[\frac{v}{k}\right]$$ lines, drinks another cup of tea, then he writes $$\left[\frac{v}{k^{2}}\right]$$ lines and so on: $$\left[\frac{v}{k^{3}}\right]$$, $$\left[\frac{v}{k^{4}}\right]$$, $$\left[\frac{v}{k^{5}}\right]$$, ...

The expression $$\left[\frac{a}{b}\right]$$ is regarded as the integral part from dividing number a by number b.

The moment the current value $$\left[\frac{v}{k\cdot p}\right]$$ equals 0, Vasya immediately falls asleep and he wakes up only in the morning, when the program should already be finished.

Vasya is wondering, what minimum allowable value v can take to let him write not less than n lines of code before he falls asleep.

## Input Format
The input consists of two integers n and k, separated by spaces — the size of the program in lines and the productivity reduction coefficient, 1 ≤ n ≤ 109, 2 ≤ k ≤ 10.

## Output Format
Print the only integer — the minimum value of v that lets Vasya write the program in one night.

## Examples
```input
7 2
```
```output
4
```
-----
```input
59 9
```
```output
54
```

## Note
In the first sample the answer is v = 4. Vasya writes the code in the following portions: first 4 lines, then 2, then 1, and then Vasya falls asleep. Thus, he manages to write 4 + 2 + 1 = 7 lines in a night and complete the task.

In the second sample the answer is v = 54. Vasya writes the code in the following portions: 54, 6. The total sum is 54 + 6 = 60, that's even more than n = 59.

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
A string is binary, if it consists only of characters "0" and "1".

String v is a substring of string w if it has a non-zero length and can be read starting from some position in string w. For example, string "010" has six substrings: "0", "1", "0", "01", "10", "010". Two substrings are considered different if their positions of occurrence are different. So, if some string occurs multiple times, we should consider it the number of times it occurs.

You are given a binary string s. Your task is to find the number of its substrings, containing exactly k characters "1".

## Input Format
The first line contains the single integer k (0 ≤ k ≤ 106). The second line contains a non-empty binary string s. The length of s does not exceed 106 characters.

## Output Format
Print the single number — the number of substrings of the given string, containing exactly k characters "1".

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

## Examples
```input
1
1010
```
```output
6
```
-----
```input
2
01010
```
```output
4
```
-----
```input
100
01010
```
```output
0
```

## Note
In the first sample the sought substrings are: "1", "1", "10", "01", "10", "010".

In the second sample the sought substrings are: "101", "0101", "1010", "01010".

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
A ticket is a string consisting of six digits. A ticket is considered lucky if the sum of the first three digits is equal to the sum of the last three digits. Given a ticket, output if it is lucky or not. Note that a ticket can have leading zeroes.

## Input Format
The first line of the input contains an integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of testcases.

The description of each test consists of one line containing one string consisting of six digits.

## Output Format
Output $$$t$$$ lines, each of which contains the answer to the corresponding test case. Output "YES" if the given ticket is lucky, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

## Examples
```input
5
213132
973894
045207
000000
055776
```
```output
YES
NO
YES
YES
NO
```

## Note
In the first test case, the sum of the first three digits is $$$2 + 1 + 3 = 6$$$ and the sum of the last three digits is $$$1 + 3 + 2 = 6$$$, they are equal so the answer is "YES".

In the second test case, the sum of the first three digits is $$$9 + 7 + 3 = 19$$$ and the sum of the last three digits is $$$8 + 9 + 4 = 21$$$, they are not equal so the answer is "NO".

In the third test case, the sum of the first three digits is $$$0 + 4 + 5 = 9$$$ and the sum of the last three digits is $$$2 + 0 + 7 = 9$$$, they are equal so the answer is "YES".

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
There are $$$n$$$ boxes with different quantities of candies in each of them. The $$$i$$$-th box has $$$a_i$$$ candies inside.

You also have $$$n$$$ friends that you want to give the candies to, so you decided to give each friend a box of candies. But, you don't want any friends to get upset so you decided to eat some (possibly none) candies from each box so that all boxes have the same quantity of candies in them. Note that you may eat a different number of candies from different boxes and you cannot add candies to any of the boxes.

What's the minimum total number of candies you have to eat to satisfy the requirements?

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 50$$$) — the number of boxes you have.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^7$$$) — the quantity of candies in each box.

## Output Format
For each test case, print a single integer denoting the minimum number of candies you have to eat to satisfy the requirements.

## Examples
```input
5
5
1 2 3 4 5
6
1000 1000 5 1000 1000 1000
10
1 2 3 5 1 2 7 9 13 5
3
8 8 8
1
10000000
```
```output
10
4975
38
0
0
```

## Note
For the first test case, you can eat $$$1$$$ candy from the second box, $$$2$$$ candies from the third box, $$$3$$$ candies from the fourth box and $$$4$$$ candies from the fifth box. Now the boxes have $$$[1, 1, 1, 1, 1]$$$ candies in them and you ate $$$0 + 1 + 2 + 3 + 4 = 10$$$ candies in total so the answer is $$$10$$$.

For the second test case, the best answer is obtained by making all boxes contain $$$5$$$ candies in them, thus eating $$$995 + 995 + 0 + 995 + 995 + 995 = 4975$$$ candies in total.

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 $$$n$$$ words of equal length $$$m$$$, consisting of lowercase Latin alphabet letters. The $$$i$$$-th word is denoted $$$s_i$$$.

In one move you can choose any position in any single word and change the letter at that position to the previous or next letter in alphabetical order. For example:

- you can change 'e' to 'd' or to 'f';
- 'a' can only be changed to 'b';
- 'z' can only be changed to 'y'.

The difference between two words is the minimum number of moves required to make them equal. For example, the difference between "best" and "cost" is $$$1 + 10 + 0 + 0 = 11$$$.

Find the minimum difference of $$$s_i$$$ and $$$s_j$$$ such that $$$(i < j)$$$. In other words, find the minimum difference over all possible pairs of the $$$n$$$ words.

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

The first line of each test case contains $$$2$$$ integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 50$$$, $$$1 \leq m \leq 8$$$) — the number of strings and their length respectively.

Then follows $$$n$$$ lines, the $$$i$$$-th of which containing a single string $$$s_i$$$ of length $$$m$$$, consisting of lowercase Latin letters.

## Output Format
For each test case, print a single integer — the minimum difference over all possible pairs of the given strings.

## Examples
```input
6
2 4
best
cost
6 3
abb
zba
bef
cdu
ooo
zzz
2 7
aaabbbc
bbaezfe
3 2
ab
ab
ab
2 8
aaaaaaaa
zzzzzzzz
3 1
a
u
y
```
```output
11
8
35
0
200
4
```

## Note
For the second test case, one can show that the best pair is ("abb","bef"), which has difference equal to $$$8$$$, which can be obtained in the following way: change the first character of the first string to 'b' in one move, change the second character of the second string to 'b' in $$$3$$$ moves and change the third character of the second string to 'b' in $$$4$$$ moves, thus making in total $$$1 + 3 + 4 = 8$$$ moves.

For the third test case, there is only one possible pair and it can be shown that the minimum amount of moves necessary to make the strings equal is $$$35$$$.

For the fourth test case, there is a pair of strings which is already equal, so the answer is $$$0$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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
The only difference between the two versions is that in this version $$$n \leq 1000$$$ and the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

A terminal is a row of $$$n$$$ equal segments numbered $$$1$$$ to $$$n$$$ in order. There are two terminals, one above the other.

You are given an array $$$a$$$ of length $$$n$$$. For all $$$i = 1, 2, \dots, n$$$, there should be a straight wire from some point on segment $$$i$$$ of the top terminal to some point on segment $$$a_i$$$ of the bottom terminal. You can't select the endpoints of a segment. For example, the following pictures show two possible wirings if $$$n=7$$$ and $$$a=[4,1,4,6,7,7,5]$$$.

A crossing occurs when two wires share a point in common. In the picture above, crossings are circled in red.

What is the maximum number of crossings there can be if you place the wires optimally?

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — the elements of the array.

The sum of $$$n$$$ across all test cases does not exceed $$$1000$$$.

## Output Format
For each test case, output a single integer — the maximum number of crossings there can be if you place the wires optimally.

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

## Note
The first test case is shown in the second picture in the statement.

In the second test case, the only wiring possible has the two wires cross, so the answer is $$$1$$$.

In the third test case, the only wiring possible has one wire, so the answer is $$$0$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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
The only difference between the two versions is that in this version $$$n \leq 2 \cdot 10^5$$$ and the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

A terminal is a row of $$$n$$$ equal segments numbered $$$1$$$ to $$$n$$$ in order. There are two terminals, one above the other.

You are given an array $$$a$$$ of length $$$n$$$. For all $$$i = 1, 2, \dots, n$$$, there should be a straight wire from some point on segment $$$i$$$ of the top terminal to some point on segment $$$a_i$$$ of the bottom terminal. You can't select the endpoints of a segment. For example, the following pictures show two possible wirings if $$$n=7$$$ and $$$a=[4,1,4,6,7,7,5]$$$.

A crossing occurs when two wires share a point in common. In the picture above, crossings are circled in red.

What is the maximum number of crossings there can be if you place the wires optimally?

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — the elements of the array.

The sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output a single integer — the maximum number of crossings there can be if you place the wires optimally.

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

## Note
The first test case is shown in the second picture in the statement.

In the second test case, the only wiring possible has the two wires cross, so the answer is $$$1$$$.

In the third test case, the only wiring possible has one wire, so the answer is $$$0$$$.

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