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
You are given a permutation$$$^\dagger$$$ $$$a$$$ of size $$$n$$$. You can do the following operation

- Select an index $$$i$$$ from $$$2$$$ to $$$n - 1$$$ such that $$$a_{i - 1} < a_i$$$ and $$$a_i > a_{i+1}$$$. Swap $$$a_i$$$ and $$$a_{i+1}$$$.

Determine whether it is possible to sort the permutation after a finite number of operations.

$$$^\dagger$$$ A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

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

The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 10$$$) — the size of the permutation.

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

## Output Format
For each test case, print "YES" if it is possible to sort the permutation, and "NO" otherwise.

You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).

## Examples
```input
6
3
1 2 3
5
1 3 2 5 4
5
5 4 3 2 1
3
3 1 2
4
2 3 1 4
5
5 1 2 3 4
```
```output
YES
YES
NO
NO
NO
NO
```

## Note
In the first test case, the permutation is already sorted.

In the second test case, we can choose index $$$i=2$$$ as $$$1<3$$$ and $$$3>2$$$ to form $$$[1, 2, 3, 5, 4]$$$. Then, we can choose index $$$i=4$$$ as $$$3<5$$$ and $$$5>4$$$ to form $$$[1, 2, 3, 4, 5]$$$.

In the third test case, it can be proven that it is impossible to sort the permutation.

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
You are given a string $$$s$$$ of length $$$n$$$ consisting of characters $$$\texttt{A}$$$ and $$$\texttt{B}$$$. You are allowed to do the following operation:

- Choose an index $$$1 \le i \le n - 1$$$ such that $$$s_i = \texttt{A}$$$ and $$$s_{i + 1} = \texttt{B}$$$. Then, swap $$$s_i$$$ and $$$s_{i+1}$$$.

You are only allowed to do the operation at most once for each index $$$1 \le i \le n - 1$$$. However, you can do it in any order you want. Find the maximum number of operations that you can carry out.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). 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 length of string $$$s$$$.

The second line of each test case contains the string $$$s$$$ ($$$s_i=\texttt{A}$$$ or $$$s_i=\texttt{B}$$$).

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, print a single integer containing the maximum number of operations that you can carry out.

## Examples
```input
3
2
AB
4
BBBA
4
AABB
```
```output
1
0
3
```

## Note
In the first test case, we can do the operation exactly once for $$$i=1$$$ as $$$s_1=\texttt{A}$$$ and $$$s_2=\texttt{B}$$$.

In the second test case, it can be proven that it is not possible to do an operation.

In the third test case, we can do an operation on $$$i=2$$$ to form $$$\texttt{ABAB}$$$, then another operation on $$$i=3$$$ to form $$$\texttt{ABBA}$$$, and finally another operation on $$$i=1$$$ to form $$$\texttt{BABA}$$$. Note that even though at the end, $$$s_2 = \texttt{A}$$$ and $$$s_3 = \texttt{B}$$$, we cannot do an operation on $$$i=2$$$ again as we can only do the operation at most once for each index.

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 $$$1$$$-indexed array $$$a$$$ of length $$$n$$$ where each element is $$$1$$$ or $$$2$$$.

Process $$$q$$$ queries of the following two types:

- "1 s": check if there exists a subarray$$$^{\dagger}$$$ of $$$a$$$ whose sum equals to $$$s$$$.
- "2 i v": change $$$a_i$$$ to $$$v$$$.

$$$^{\dagger}$$$ An array $$$b$$$ is a subarray of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

## Input Format
Each test contains 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 two integers $$$n$$$ and $$$q$$$ ($$$1\le n,q\le 10^5$$$) — the length of array $$$a$$$ and the number of queries.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$a_i$$$ is $$$1$$$ or $$$2$$$) — the elements of array $$$a$$$.

Each of the following $$$q$$$ lines of each test case contains some integers. The first integer $$$\mathrm{op}$$$ is either $$$1$$$ or $$$2$$$.

- If $$$\mathrm{op}$$$ is $$$1$$$, it is followed by one integer $$$s$$$ ($$$1 \leq s \leq 2n$$$).
- If $$$\mathrm{op}$$$ is $$$2$$$, it is followed by two integers $$$i$$$ and $$$v$$$ ($$$1 \leq i \leq n$$$, $$$v$$$ is $$$1$$$ or $$$2$$$).

It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases both do not exceed $$$10^5$$$.

## Output Format
For each query with $$$\mathrm{op}=1$$$, output "YES" in one line if there exists a subarray of $$$a$$$ whose sum is equals to $$$s$$$, otherwise output "NO".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

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

## Note
Consider the first example:

- The answer for the first query is "YES" because $$$a_1+a_2+a_3=2+1+2=5$$$.
- The answer for the second query is "YES" because $$$a_1+a_2+a_3+a_4=2+1+2+1=6$$$.
- The answer for the third query is "NO" because we cannot find any subarray of $$$a$$$ whose sum is $$$7$$$.
- After the fourth query, the array $$$a$$$ becomes $$$[2,1,2,2,2]$$$.
- The answer for the fifth query is "YES" because $$$a_2+a_3+a_4+a_5=1+2+2+2=7$$$.

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
Theofanis is busy after his last contest, as now, he has to deliver many halloumis all over the world. He stored them inside $$$n$$$ boxes and each of which has some number $$$a_i$$$ written on it.

He wants to sort them in non-decreasing order based on their number, however, his machine works in a strange way. It can only reverse any subarray$$$^{\dagger}$$$ of boxes with length at most $$$k$$$.

Find if it's possible to sort the boxes using any number of reverses.

$$$^{\dagger}$$$ Reversing a subarray means choosing two indices $$$i$$$ and $$$j$$$ (where $$$1 \le i \le j \le n$$$) and changing the array $$$a_1, a_2, \ldots, a_n$$$ to $$$a_1, a_2, \ldots, a_{i-1}, \; a_j, a_{j-1}, \ldots, a_i, \; a_{j+1}, \ldots, a_{n-1}, a_n$$$. The length of the subarray is then $$$j - i + 1$$$.

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

Each test case consists of two lines.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 100$$$) — the number of boxes and the length of the maximum reverse that Theofanis can make.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$) — the number written on each box.

## Output Format
For each test case, print YES (case-insensitive), if the array can be sorted in non-decreasing order, or NO (case-insensitive) otherwise.

## Examples
```input
5
3 2
1 2 3
3 1
9 9 9
4 4
6 4 2 1
4 3
10 3 830 14
2 1
3 1
```
```output
YES
YES
YES
YES
NO
```

## Note
In the first two test cases, the boxes are already sorted in non-decreasing order.

In the third test case, we can reverse the whole array.

In the fourth test case, we can reverse the first two boxes and the last two boxes.

In the fifth test case, it can be shown that it's impossible to sort the boxes.

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
Theofanis easily gets obsessed with problems before going to sleep and often has nightmares about them. To deal with his obsession he visited his doctor, Dr. Emix.

In his latest nightmare, he has an array $$$a$$$ of size $$$n$$$ and wants to divide it into non-empty subarrays$$$^{\dagger}$$$ such that every element is in exactly one of the subarrays.

For example, the array $$$[1,-3,7,-6,2,5]$$$ can be divided to $$$[1] [-3,7] [-6,2] [5]$$$.

The Cypriot value of such division is equal to $$$\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i$$$ where $$$k$$$ is the number of subarrays that we divided the array into and $$$\mathrm{sum}_i$$$ is the sum of the $$$i$$$-th subarray.

The Cypriot value of this division of the array $$$[1] [-3,7] [-6,2] [5] = 1 \cdot 1 + 2 \cdot (-3 + 7) + 3 \cdot (-6 + 2) + 4 \cdot 5 = 17$$$.

Theofanis is wondering what is the maximum Cypriot value of any division of the array.

$$$^{\dagger}$$$ An array $$$b$$$ is a subarray of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

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

Each test case consists of two lines.

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^8 \le a_i \le 10^{8}$$$) — the elements of the array.

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, print one integer — the maximum Cypriot value of the array $$$a$$$.

## Examples
```input
4
6
1 -3 7 -6 2 5
4
2 9 -5 -3
8
-3 -4 2 -5 1 10 17 23
1
830
```
```output
32
4
343
830
```

## Note
In the first test case, to get the maximum Cypriot value we divide the array into $$$[1][-3][7][-6][2][5]$$$ which gives us: $$$\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i = 1 \cdot 1 + 2 \cdot (-3) + 3 \cdot 7 + 4 \cdot (-6) + 5 \cdot 2 + 6 \cdot 5 = 32$$$

Similarly, in the second test case we divide the array into $$$[2][9,-5,-3]$$$ which gives us $$$\Sigma_{i=1}^{k} i \cdot \mathrm{sum}_i = 1 \cdot 2 + 2 \cdot (9 + (-5) + (-3)) = 4$$$.

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

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
This is the easy version of the problem. The only difference between the two versions is the constraint on $$$n$$$ and $$$q$$$, the memory and time limits. You can make hacks only if all versions of the problem are solved.

Theofanis really likes to play with the bits of numbers. He has an array $$$a$$$ of size $$$n$$$ and an integer $$$k$$$. He can make at most $$$k$$$ operations in the array. In each operation, he picks a single element and increases it by $$$1$$$.

He found the maximum bitwise AND that array $$$a$$$ can have after at most $$$k$$$ operations.

Theofanis has put a lot of work into finding this value and was very happy with his result. Unfortunately, Adaś, being the evil person that he is, decided to bully him by repeatedly changing the value of $$$k$$$.

Help Theofanis by calculating the maximum possible bitwise AND for $$$q$$$ different values of $$$k$$$. Note that queries are independent.

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 10^5$$$ and $$$n \cdot q \le 10^5$$$) — the size of the array and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^6$$$) — the elements of the array.

Next $$$q$$$ lines describe the queries. The $$$i$$$-th line contains one integer $$$k_i$$$ ($$$0 \le k_i \le 10^{18}$$$) — the number of operations that can be done in the $$$i$$$-th query.

## Output Format
For each query, print one integer — the maximum bitwise AND that array $$$a$$$ can have after at most $$$k_i$$$ operations.

## Examples
```input
4 2
1 3 7 5
2
10
```
```output
2
6
```
-----
```input
3 5
4 0 2
9
8
17
1
3
```
```output
5
4
7
0
1
```
-----
```input
1 2
10
5
2318381298321
```
```output
15
2318381298331
```

## Note
In the first test case, in the first query, we add $$$1$$$ in the first and last elements of the array.

Thus, the array becomes $$$[2,3,7,6]$$$ with bitwise AND equal to $$$2$$$.

In the second test case, in the first query, we add $$$1$$$ in the first element, $$$5$$$ in the second, and $$$3$$$ in the third and now all the elements are equal to $$$5$$$.

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

# Problem
This is the hard version of the problem. The only difference between the two versions is the constraint on $$$n$$$ and $$$q$$$, the memory and time limits. You can make hacks only if all versions of the problem are solved.

Theofanis really likes to play with the bits of numbers. He has an array $$$a$$$ of size $$$n$$$ and an integer $$$k$$$. He can make at most $$$k$$$ operations in the array. In each operation, he picks a single element and increases it by $$$1$$$.

He found the maximum bitwise AND that array $$$a$$$ can have after at most $$$k$$$ operations.

Theofanis has put a lot of work into finding this value and was very happy with his result. Unfortunately, Adaś, being the evil person that he is, decided to bully him by repeatedly changing the value of $$$k$$$.

Help Theofanis by calculating the maximum possible bitwise AND for $$$q$$$ different values of $$$k$$$. Note that queries are independent.

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 10^6$$$) — the size of the array and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^6$$$) — the elements of the array.

Next $$$q$$$ lines describe the queries. The $$$i$$$-th line contains one integer $$$k_i$$$ ($$$0 \le k_i \le 10^{18}$$$) — the number of operations that can be done in the $$$i$$$-th query.

## Output Format
For each query, print one integer — the maximum bitwise AND that array $$$a$$$ can have after at most $$$k_i$$$ operations.

## Examples
```input
4 2
1 3 7 5
2
10
```
```output
2
6
```
-----
```input
3 5
4 0 2
9
8
17
1
3
```
```output
5
4
7
0
1
```
-----
```input
1 2
10
5
2318381298321
```
```output
15
2318381298331
```

## Note
In the first test case, in the first query, we add $$$1$$$ in the first and last elements of the array.

Thus, the array becomes $$$[2,3,7,6]$$$ with bitwise AND equal to $$$2$$$.

In the second test case, in the first query, we add $$$1$$$ in the first element, $$$5$$$ in the second, and $$$3$$$ in the third and now all the elements are equal to $$$5$$$.

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

# Problem
Theofanis wants to play video games, however he should also take care of his sister. Since Theofanis is a CS major, he found a way to do both. He will install some cameras in his house in order to make sure his sister is okay.

His house is an undirected graph with $$$n$$$ nodes and $$$m$$$ edges. His sister likes to play at the edges of the graph, so he has to install a camera to at least one endpoint of every edge of the graph. Theofanis wants to find a vertex cover that maximizes the minimum difference between indices of the chosen nodes.

More formally, let $$$a_1, a_2, \ldots, a_k$$$ be a vertex cover of the graph. Let the minimum difference between indices of the chosen nodes be the minimum $$$\lvert a_i - a_j \rvert$$$ (where $$$i \neq j$$$) out of the nodes that you chose. If $$$k = 1$$$ then we assume that the minimum difference between indices of the chosen nodes is $$$n$$$.

Can you find the maximum possible minimum difference between indices of the chosen nodes over all vertex covers?

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^{5}, 1 \le m \le 2 \cdot 10^{5}$$$) — the number of nodes and the number of edges.

The $$$i$$$-th of the following $$$m$$$ lines in the test case contains two positive integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$), meaning that there exists an edge between them in the graph.

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

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

## Output Format
For each test case, print the maximum minimum difference between indices of the chosen nodes over all vertex covers.

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

## Note
In the first test case, we can install cameras at nodes $$$1$$$, $$$3$$$, and $$$7$$$, so the answer is $$$2$$$.

In the second test case, we can install only one camera at node $$$1$$$, so the answer is $$$3$$$.

Now solve the problem and return the code.