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

# Problem
In order to write a string, Atilla needs to first learn all letters that are contained in the string.

Atilla needs to write a message which can be represented as a string $$$s$$$. He asks you what is the minimum alphabet size required so that one can write this message.

The alphabet of size $$$x$$$ ($$$1 \leq x \leq 26$$$) contains only the first $$$x$$$ Latin letters. For example an alphabet of size $$$4$$$ contains only the characters $$$\texttt{a}$$$, $$$\texttt{b}$$$, $$$\texttt{c}$$$ and $$$\texttt{d}$$$.

## Input Format
The first line contains a single 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 \leq n \leq 100$$$) — the length of the string.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$, consisting of lowercase Latin letters.

## Output Format
For each test case, output a single integer — the minimum alphabet size required to so that Atilla can write his message $$$s$$$.

## Examples
```input
5
1
a
4
down
10
codeforces
3
bcf
5
zzzzz
```
```output
1
23
19
6
26
```

## Note
For the first test case, Atilla needs to know only the character $$$\texttt{a}$$$, so the alphabet of size $$$1$$$ which only contains $$$\texttt{a}$$$ is enough.

For the second test case, Atilla needs to know the characters $$$\texttt{d}$$$, $$$\texttt{o}$$$, $$$\texttt{w}$$$, $$$\texttt{n}$$$. The smallest alphabet size that contains all of them is $$$23$$$ (such alphabet can be represented as the string $$$\texttt{abcdefghijklmnopqrstuvw}$$$).

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
There are $$$n$$$ participants in a competition, participant $$$i$$$ having a strength of $$$s_i$$$.

Every participant wonders how much of an advantage they have over the other best participant. In other words, each participant $$$i$$$ wants to know the difference between $$$s_i$$$ and $$$s_j$$$, where $$$j$$$ is the strongest participant in the competition, not counting $$$i$$$ (a difference can be negative).

So, they ask you for your help! For each $$$i$$$ ($$$1 \leq i \leq n$$$) output the difference between $$$s_i$$$ and the maximum strength of any participant other than participant $$$i$$$.

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

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

The following line contains $$$n$$$ space-separated positive integers $$$s_1$$$, $$$s_2$$$, ..., $$$s_n$$$ ($$$1 \leq s_i \leq 10^9$$$) — the strengths of the participants.

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

## Output Format
For each test case, output $$$n$$$ space-separated integers. For each $$$i$$$ ($$$1 \leq i \leq n$$$) output the difference between $$$s_i$$$ and the maximum strength of any other participant.

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

## Note
For the first test case:

- The first participant has a strength of $$$4$$$ and the largest strength of a participant different from the first one is $$$7$$$, so the answer for the first participant is $$$4 - 7 = -3$$$.
- The second participant has a strength of $$$7$$$ and the largest strength of a participant different from the second one is $$$5$$$, so the answer for the second participant is $$$7 - 5 = 2$$$.
- The third participant has a strength of $$$3$$$ and the largest strength of a participant different from the third one is $$$7$$$, so the answer for the third participant is $$$3 - 7 = -4$$$.
- The fourth participant has a strength of $$$5$$$ and the largest strength of a participant different from the fourth one is $$$7$$$, so the answer for the fourth participant is $$$5 - 7 = -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 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 an array $$$a[0 \dots n-1]$$$ of $$$n$$$ integers. This array is called a "valley" if there exists exactly one subarray $$$a[l \dots r]$$$ such that:

- $$$0 \le l \le r \le n-1$$$,
- $$$a_l = a_{l+1} = a_{l+2} = \dots = a_r$$$,
- $$$l = 0$$$ or $$$a_{l-1} > a_{l}$$$,
- $$$r = n-1$$$ or $$$a_r < a_{r+1}$$$.

Here are three examples:

The first image shows the array [$$$3, 2, 2, 1, 2, 2, 3$$$], it is a valley because only subarray with indices $$$l=r=3$$$ satisfies the condition.

The second image shows the array [$$$1, 1, 1, 2, 3, 3, 4, 5, 6, 6, 6$$$], it is a valley because only subarray with indices $$$l=0, r=2$$$ satisfies the codition.

The third image shows the array [$$$1, 2, 3, 4, 3, 2, 1$$$], it is not a valley because two subarrays $$$l=r=0$$$ and $$$l=r=6$$$ that satisfy the condition.

You are asked whether the given array is a valley or not.

Note that we consider the array to be indexed from $$$0$$$.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases is smaller than $$$2\cdot10^5$$$.

## Output Format
For each test case, output "YES" (without quotes) if the array is a valley, and "NO" (without quotes) 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
6
7
3 2 2 1 2 2 3
11
1 1 1 2 3 3 4 5 6 6 6
7
1 2 3 4 3 2 1
7
9 7 4 6 9 9 10
1
1000000000
8
9 4 4 5 9 4 9 10
```
```output
YES
YES
NO
YES
YES
NO
```

## Note
The first three test cases are explained in the statement.

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 binary array$$$^{\dagger}$$$ of length $$$n$$$. You are allowed to perform one operation on it at most once. In an operation, you can choose any element and flip it: turn a $$$0$$$ into a $$$1$$$ or vice-versa.

What is the maximum number of inversions$$$^{\ddagger}$$$ the array can have after performing at most one operation?

$$$^\dagger$$$ A binary array is an array that contains only zeroes and ones.

$$$^\ddagger$$$ The number of inversions in an array is the number of pairs of indices $$$i,j$$$ such that $$$i<j$$$ and $$$a_i > a_j$$$.

## Input Format
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.

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

The following line contains $$$n$$$ space-separated positive integers $$$a_1$$$, $$$a_2$$$,..., $$$a_n$$$ ($$$0 \leq a_i \leq 1$$$) — the elements of the array.

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

## Output Format
For each test case, output a single integer  — the maximum number of inversions the array can have after performing at most one operation.

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

## Note
For the first test case, the inversions are initially formed by the pairs of indices ($$$1, 2$$$), ($$$1, 4$$$), ($$$3, 4$$$), being a total of $$$3$$$, which already is the maximum possible.

For the second test case, the inversions are initially formed by the pairs of indices ($$$2, 3$$$), ($$$2, 4$$$), ($$$2, 6$$$), ($$$5, 6$$$), being a total of four. But, by flipping the first element, the array becomes $$${1, 1, 0, 0, 1, 0}$$$, which has the inversions formed by the pairs of indices ($$$1, 3$$$), ($$$1, 4$$$), ($$$1, 6$$$), ($$$2, 3$$$), ($$$2, 4$$$), ($$$2, 6$$$), ($$$5, 6$$$) which total to $$$7$$$ inversions which is the maximum possible.

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
Doremy has $$$n$$$ buckets of paint which is represented by an array $$$a$$$ of length $$$n$$$. Bucket $$$i$$$ contains paint with color $$$a_i$$$.

Let $$$c(l,r)$$$ be the number of distinct elements in the subarray $$$[a_l,a_{l+1},\ldots,a_r]$$$. Choose $$$2$$$ integers $$$l$$$ and $$$r$$$ such that $$$l \leq r$$$ and $$$r-l-c(l,r)$$$ is maximized.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$).

It is guaranteed that the sum of $$$n$$$ does not exceed $$$10^5$$$.

## Output Format
For each test case, output $$$l$$$ and $$$r$$$ such that $$$l \leq r$$$ and $$$r-l-c(l,r)$$$ is maximized.

If there are multiple solutions, you may output any.

## Examples
```input
7
5
1 3 2 2 4
5
1 2 3 4 5
4
2 1 2 1
3
2 3 3
2
2 2
1
1
9
9 8 5 2 1 1 2 3 3
```
```output
2 4
1 5
1 4
2 3
1 2
1 1
3 9
```

## Note
In the first test case, $$$a=[1,3,2,2,4]$$$.

- When $$$l=1$$$ and $$$r=3$$$, $$$c(l,r)=3$$$ (there are $$$3$$$ distinct elements in $$$[1,3,2]$$$).
- When $$$l=2$$$ and $$$r=4$$$, $$$c(l,r)=2$$$ (there are $$$2$$$ distinct elements in $$$[3,2,2]$$$).

It can be shown that choosing $$$l=2$$$ and $$$r=4$$$ maximizes the value of $$$r-l-c(l,r)$$$ at $$$0$$$.

For the second test case, $$$a=[1,2,3,4,5]$$$.

- When $$$l=1$$$ and $$$r=5$$$, $$$c(l,r)=5$$$ (there are $$$5$$$ distinct elements in $$$[1,2,3,4,5]$$$).
- When $$$l=3$$$ and $$$r=3$$$, $$$c(l,r)=1$$$ (there is $$$1$$$ distinct element in $$$[3]$$$).

It can be shown that choosing $$$l=1$$$ and $$$r=5$$$ maximizes the value of $$$r-l-c(l,r)$$$ at $$$-1$$$. Choosing $$$l=3$$$ and $$$r=3$$$ is also acceptable.

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
"Everybody! Doremy's Perfect Math Class is about to start! Come and do your best if you want to have as much IQ as me!" In today's math class, Doremy is teaching everyone subtraction. Now she gives you a quiz to prove that you are paying attention in class.

You are given a set $$$S$$$ containing positive integers. You may perform the following operation some (possibly zero) number of times:

- choose two integers $$$x$$$ and $$$y$$$ from the set $$$S$$$ such that $$$x > y$$$ and $$$x - y$$$ is not in the set $$$S$$$.
- add $$$x-y$$$ into the set $$$S$$$.

You need to tell Doremy the maximum possible number of integers in $$$S$$$ if the operations are performed optimally. It can be proven that this number is finite.

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

The first line contains an integer $$$n$$$ ($$$2 \le n\le 10^5$$$) — the size of the set $$$S$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$1\le a_1 < a_2 < \cdots < a_n \le 10^9$$$) — the positive integers in $$$S$$$.

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

## Output Format
For each test case, you need to output the maximum possible number of integers in $$$S$$$. It can be proven that this value is finite.

## Examples
```input
2
2
1 2
3
5 10 25
```
```output
2
5
```

## Note
In the first test case, no such $$$x$$$ and $$$y$$$ exist. The maximum possible number of integers in $$$S$$$ is $$$2$$$.

In the second test case,

- $$$S=\{5,10,25\}$$$ at first. You can choose $$$x=25$$$, $$$y=10$$$, then add $$$x-y=15$$$ to the set.
- $$$S=\{5,10,15,25\}$$$ now. You can choose $$$x=25$$$, $$$y=5$$$, then add $$$x-y=20$$$ to the set.
- $$$S=\{5,10,15,20,25\}$$$ now. You can not perform any operation now.

After performing all operations, the number of integers in $$$S$$$ is $$$5$$$. It can be proven that no other sequence of operations allows $$$S$$$ to contain more than $$$5$$$ integers.

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
Doremy's new city is under construction! The city can be regarded as a simple undirected graph with $$$n$$$ vertices. The $$$i$$$-th vertex has altitude $$$a_i$$$. Now Doremy is deciding which pairs of vertices should be connected with edges.

Due to economic reasons, there should be no self-loops or multiple edges in the graph.

Due to safety reasons, there should not be pairwise distinct vertices $$$u$$$, $$$v$$$, and $$$w$$$ such that $$$a_u \leq a_v \leq a_w$$$ and the edges $$$(u,v)$$$ and $$$(v,w)$$$ exist.

Under these constraints, Doremy would like to know the maximum possible number of edges in the graph. Can you help her?

Note that the constructed graph is allowed to be disconnected.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1\le a_i\le 10^6$$$) — the altitudes of each vertex.

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

## Output Format
For each test case, output the maximum possible number of edges in the graph.

## Examples
```input
4
4
2 2 3 1
6
5 2 3 1 5 2
12
7 2 4 9 1 4 6 3 7 4 2 3
4
1000000 1000000 1000000 1000000
```
```output
3
9
35
2
```

## Note
In the first test case, there can only be at most $$$3$$$ edges in the graph. A possible construction is to connect $$$(1,3)$$$, $$$(2,3)$$$, $$$(3,4)$$$. In the picture below the red number above node $$$i$$$ is $$$a_i$$$.

The following list shows all such $$$u$$$, $$$v$$$, $$$w$$$ that the edges $$$(u,v)$$$ and $$$(v,w)$$$ exist.

- $$$u=1$$$, $$$v=3$$$, $$$w=2$$$;
- $$$u=1$$$, $$$v=3$$$, $$$w=4$$$;
- $$$u=2$$$, $$$v=3$$$, $$$w=1$$$;
- $$$u=2$$$, $$$v=3$$$, $$$w=4$$$;
- $$$u=4$$$, $$$v=3$$$, $$$w=1$$$;
- $$$u=4$$$, $$$v=3$$$, $$$w=2$$$.

Another possible construction is to connect $$$(1,4)$$$, $$$(2,4)$$$, $$$(3,4)$$$.

An unacceptable construction is to connect $$$(1,3)$$$, $$$(2,3)$$$, $$$(2,4)$$$, $$$(3,4)$$$. Because when $$$u=4$$$, $$$v=2$$$, $$$w=3$$$, $$$a_u\le a_v \le a_w$$$ holds, and the respective edges exist.

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.5 seconds
Memory limit: 512.0 MB

# Problem
Doremy has $$$n+1$$$ pegs. There are $$$n$$$ red pegs arranged as vertices of a regular $$$n$$$-sided polygon, numbered from $$$1$$$ to $$$n$$$ in anti-clockwise order. There is also a blue peg of slightly smaller diameter in the middle of the polygon. A rubber band is stretched around the red pegs.

Doremy is very bored today and has decided to play a game. Initially, she has an empty array $$$a$$$. While the rubber band does not touch the blue peg, she will:

1. choose $$$i$$$ ($$$1 \leq i \leq n$$$) such that the red peg $$$i$$$ has not been removed;
2. remove the red peg $$$i$$$;
3. append $$$i$$$ to the back of $$$a$$$.

Doremy wonders how many possible different arrays $$$a$$$ can be produced by the following process. Since the answer can be big, you are only required to output it modulo $$$p$$$. $$$p$$$ is guaranteed to be a prime number.

game with $$$n=9$$$ and $$$a=[7,5,2,8,3,9,4]$$$ and another game with $$$n=8$$$ and $$$a=[3,4,7,1,8,5,2]$$$

## Input Format
The first line contains two integers $$$n$$$ and $$$p$$$ ($$$3 \leq n \leq 5000$$$, $$$10^8 \le p \le 10^9$$$) — the number of red pegs and the modulo respectively.

$$$p$$$ is guaranteed to be a prime number.

## Output Format
Output a single integer, the number of different arrays $$$a$$$ that can be produced by the process described above modulo $$$p$$$.

## Examples
```input
4 100000007
```
```output
16
```
-----
```input
1145 141919831
```
```output
105242108
```

## Note
In the first test case, $$$n=4$$$, some possible arrays $$$a$$$ that can be produced are $$$[4,2,3]$$$ and $$$[1,4]$$$. However, it is not possible for $$$a$$$ to be $$$[1]$$$ or $$$[1,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: 4.0 seconds
Memory limit: 256.0 MB

# Problem
Doremy has $$$n$$$ buckets of paint which is represented by an array $$$a$$$ of length $$$n$$$. Bucket $$$i$$$ contains paint with color $$$a_i$$$. Initially, $$$a_i=i$$$.

Doremy has $$$m$$$ segments $$$[l_i,r_i]$$$ ($$$1 \le l_i \le r_i \le n$$$). Each segment describes an operation. Operation $$$i$$$ is performed as follows:

- For each $$$j$$$ such that $$$l_i < j \leq r_i$$$, set $$$a_j := a_{l_i}$$$.

Doremy also selects an integer $$$k$$$. She wants to know for each integer $$$x$$$ from $$$0$$$ to $$$m-1$$$, the number of distinct colors in the array after performing operations $$$x \bmod m +1, (x+1) \bmod m + 1, \ldots, (x+k-1) \bmod m +1$$$. Can you help her calculate these values? Note that for each $$$x$$$ individually we start from the initial array and perform only the given $$$k$$$ operations in the given order.

## Input Format
The first line of input contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1\le n,m\le 2\cdot 10^5$$$, $$$1 \le k \le m$$$) — the length of the array $$$a$$$, the total number of operations, and the integer that Doremy selects.

The $$$i$$$-th line of the following $$$m$$$ lines contains two integers $$$l_i$$$, $$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$) — the bounds of the $$$i$$$-th segment.

## Output Format
Output $$$m$$$ integers. The $$$(x+1)$$$-th integer should be the number of distinct colors in the array if we start from the initial array and perform operations $$$x \bmod m +1, (x+1) \bmod m + 1, \ldots, (x+k-1) \bmod m +1$$$.

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

## Note
In the first test case, the picture below shows the resulting array for the values of $$$x=0,1,2$$$ respectively.

Now solve the problem and return the code.