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
Given two arrays of distinct positive integers $$$a$$$ and $$$b$$$ of length $$$n$$$, we would like to make both the arrays the same. Two arrays $$$x$$$ and $$$y$$$ of length $$$k$$$ are said to be the same when for all $$$1 \le i \le k$$$, $$$x_i = y_i$$$.

Now in one move, you can choose some index $$$l$$$ and $$$r$$$ in $$$a$$$ ($$$l \le r$$$) and swap $$$a_l$$$ and $$$a_r$$$, then choose some $$$p$$$ and $$$q$$$ ($$$p \le q$$$) in $$$b$$$ such that $$$r-l=q-p$$$ and swap $$$b_p$$$ and $$$b_q$$$.

Is it possible to make both arrays the same?

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$). 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 arrays $$$a$$$ and $$$b$$$.

The second line of each test case contains $$$n$$$ distinct integers $$$a_1,a_2,a_3,\ldots,a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — the integers in the array $$$a$$$.

The third line of each test case contains $$$n$$$ distinct integers $$$b_1,b_2,b_3,\ldots,b_n$$$ ($$$1 \le b_i \le 2 \cdot 10^5$$$) — the integers in the array $$$b$$$.

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

## Output Format
For each testcase, print "YES" if the arrays $$$a$$$ and $$$b$$$ can be made the same. Otherwise, print "NO". 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
6
4
1 2 3 4
1 2 3 4
5
1 3 4 2 5
7 1 2 5 4
4
1 2 3 4
4 3 2 1
3
1 2 3
1 3 2
5
1 5 7 1000 4
4 1 7 5 1000
3
1 4 2
1 3 2
```
```output
YES
NO
YES
NO
NO
NO
```

## Note
In the first testcase, you don't need to perform any operations since the arrays are same.

In the second testcase, it can be proven there exists no way to make the arrays same.

In the third testcase, one of the ways to make the arrays same is to first choose $$$l=1$$$, $$$r=3$$$, $$$p=1$$$, $$$q=3$$$ then choose $$$l=1$$$, $$$r=2$$$, $$$p=3$$$, $$$q=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: 4.0 seconds
Memory limit: 256.0 MB

# Problem
You have an array of non-negative integers $$$a_1, a_2, \ldots, a_n$$$.

The value of a sub-array of length $$$\ge 2$$$, $$$a[l, r] = [a_l, a_{l+1}, \ldots, a_r]$$$ is the minimum value of $$$a_i \oplus a_j$$$ such that $$$l \le i < j \le r$$$, where $$$\oplus$$$ is the xor (exclusive-or) operator.

You have to find the $$$k$$$-th smallest value over all sub-arrays of length $$$\ge 2$$$.

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

The first line of each test case contains integer numbers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le \frac{n\cdot(n-1)}{2}$$$).

The second line of the input contains $$$n$$$ non-negative integer numbers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the array itself.

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

## Output Format
Print the $$$k$$$-th smallest value obtained over all subarrays of length at least $$$2$$$.

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

## Note
In the first testcase, we have subarrays with their smallest exclusive-or pair as:

$$$[1,2]: 3$$$

$$$[2,3]: 1$$$

$$$[3,4]: 7$$$

$$$[4,5]: 1$$$

$$$[1,2,3]: 1$$$

$$$[2,3,4]: 1$$$

$$$[3,4,5]: 1$$$

$$$[1,2,3,4]: 1$$$

$$$[2,3,4,5]: 1$$$

$$$[1,2,3,4,5]: 1$$$

The sorted order would be: $$$1, 1, 1, 1, 1, 1, 1, 1, 3, 7$$$. Therefore, the second smallest element would be $$$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 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
Oh no, the ForceCodes servers are running out of memory! Luckily, you can help them out by uploading some of your RAM!

You want to upload $$$n$$$ GBs of RAM. Every second, you will upload either $$$0$$$ or $$$1$$$ GB of RAM. However, there is a restriction on your network speed: in any $$$k$$$ consecutive seconds, you can upload only at most $$$1$$$ GB of RAM in total.

Find the minimum number of seconds needed to upload $$$n$$$ GBs of RAM!

## Input Format
Each test contains multiple test cases. The first line of input 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 and only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 100$$$) — the number of GBs that you want to upload and the length of the time window respectively.

## Output Format
For each test case, output a single integer — the minimum number of seconds needed to upload $$$n$$$ GBs of RAM.

## Examples
```input
6
5 1
2 2
2 3
1 7
11 5
100 100
```
```output
5
3
4
1
51
9901
```

## Note
In the first test case, you can upload $$$1$$$ GB of RAM per second, so to upload $$$5$$$ GBs, you need $$$5$$$ seconds.

In the second test case, you can upload $$$1$$$ GB in the first second, $$$0$$$ GBs in the second second, and $$$1$$$ GB in the third second, which in total adds up to exactly $$$2$$$ GBs of uploaded RAM.

In the third test case, you can upload $$$1$$$ GB in the first second, $$$0$$$ GBs in the second second, $$$0$$$ GBs in the third second, and $$$1$$$ GB in the fourth second, which in total adds up to exactly $$$2$$$ GBs of uploaded RAM.

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 an array of integers $$$a$$$ of length $$$n$$$.

You can apply the following operation any number of times (maybe, zero):

- First, choose an integer $$$k$$$ such that $$$1 \le k \le n$$$ and pay $$$k + 1$$$ coins.
- Then, choose exactly $$$k$$$ indices such that $$$1 \le i_1 < i_2 < \ldots < i_k \le n$$$.
- Then, for each $$$x$$$ from $$$1$$$ to $$$k$$$, increase $$$a_{i_x}$$$ by $$$1$$$.

Find the minimum number of coins needed to make $$$a$$$ non-decreasing. That is, $$$a_1 \le a_2 \le \ldots \le a_n$$$.

## Input Format
Each test contains multiple test cases. The first line of input 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 10^9$$$) — the elements of the array $$$a$$$.

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

## Output Format
For each test case, output a single integer — the minimum number of coins needed to make $$$a$$$ non-decreasing.

## Examples
```input
5
3
1 7 9
5
2 1 4 7 6
4
1 3 2 4
1
179
9
344 12 37 60 311 613 365 328 675
```
```output
0
3
2
0
1821
```

## Note
In the first test case, $$$a$$$ is already sorted, so you don't have to spend any coins.

In the second test case, the optimal sequence of operations is:

- Choose $$$k = 2$$$ and the indices $$$2$$$ and $$$5$$$: $$$[ 2, \color{red}{1}, 4, 7, \color{red}{6} ] \rightarrow [2, 2, 4, 7, 7]$$$. This costs $$$3$$$ coins.

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$$$ flowers in a row, the $$$i$$$-th of them initially has a positive height of $$$h_i$$$ meters.

Every second, the wind will blow from the left, causing the height of some flowers to decrease.

Specifically, every second, for each $$$i$$$ from $$$1$$$ to $$$n$$$, in this order, the following happens:

- If $$$i = n$$$ or $$$h_i > h_{i + 1}$$$, the value of $$$h_i$$$ changes to $$$\max(0, h_i - 1)$$$.

How many seconds will pass before $$$h_i=0$$$ for all $$$1 \le i \le n$$$ for the first time?

## Input Format
Each test contains multiple test cases. The first line of input 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 number of flowers.

The second line of each test case contains $$$n$$$ integers $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10 ^ 9$$$) — the heights of the flowers.

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

## Output Format
For each test case, output a single integer — the number of seconds that will pass before $$$h_i=0$$$ for all $$$1 \le i \le n$$$.

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

## Note
In the first test case, the flower heights change as follows: $$$[1, 1, 2] \rightarrow [1, 1, 1] \rightarrow [1, 1, 0] \rightarrow [1, 0, 0] \rightarrow [0, 0, 0]$$$.

In the second test case, the flower heights change as follows: $$$[3, 1] \rightarrow [2, 0] \rightarrow [1, 0] \rightarrow [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
Alice and Bob are playing a game. Initially, there are $$$n$$$ cakes, with the $$$i$$$-th cake having a tastiness value of $$$a_i$$$.

Alice and Bob take turns eating them, with Alice starting first:

- In her turn, Alice chooses and eats any remaining cake whose tastiness is strictly greater than the maximum tastiness of any of the cakes she's eaten before that. Note that on the first turn, she can choose any cake.
- In his turn, Bob chooses any remaining cake and eats it.

The game ends when the current player can't eat a suitable cake. Let $$$x$$$ be the number of cakes that Alice ate. Then, Alice wants to maximize $$$x$$$, while Bob wants to minimize $$$x$$$.

Find out how many cakes Alice will eat if both players play optimally.

## Input Format
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 500$$$) — 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 5000$$$) — the number of cakes.

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

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

## Output Format
For each test case, output a single integer — the number of cakes Alice will eat if both players play optimally.

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

## Note
In the first test case, one possible sequence of turns is:

1. Alice eats a cake with a tastiness value of $$$1$$$. The remaining cakes are $$$[4, 2, 3]$$$.
2. Bob eats a cake with a tastiness value of $$$2$$$. The remaining cakes are $$$[4, 3]$$$.
3. Alice eats a cake with a tastiness of $$$3$$$. The remaining cakes are $$$[4]$$$.
4. Bob eats a cake with a tastiness value of $$$4$$$. The remaining cakes are $$$[]$$$.
5. Since there are no more cakes left, the game ends.

In the second test case, one possible sequence of turns is:

1. Alice eats a cake with a tastiness value of $$$1$$$. The remaining cakes are $$$[1, 1]$$$.
2. Bob eats a cake with a tastiness value of $$$1$$$. The remaining cakes are $$$[1]$$$.
3. Since Alice has already eaten a cake with a tastiness value of $$$1$$$, she cannot make a turn, so the game ends.

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$$$. You can make hacks only if both versions of the problem are solved.

You are given an array of integers $$$a$$$ of length $$$n$$$.

In one operation, you will perform the following two-step process:

1. Choose an index $$$i$$$ such that $$$1 \le i < |a|$$$ and $$$a_i = i$$$.
2. Remove $$$a_i$$$ and $$$a_{i+1}$$$ from the array and concatenate the remaining parts.

Find the maximum number of times that you can perform the operation above.

## Input Format
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — 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 100$$$) — 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$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$100$$$.

## Output Format
For each test case, output a single integer — the maximum number of times that you can perform the operation.

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

## Note
In the first test case, one possible optimal sequence of operations is $$$[ 1, 5, \color{red}{3}, \color{red}{2}, 4 ] \rightarrow [\color{red}{1}, \color{red}{5}, 4] \rightarrow [4]$$$.

In the third test case, one possible optimal sequence of operations is $$$[1, \color{red}{2}, \color{red}{3}] \rightarrow [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 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: 0.5 seconds
Memory limit: 256.0 MB

# Problem
The Little Elephant loves sortings.

He has an array a consisting of n integers. Let's number the array elements from 1 to n, then the i-th element will be denoted as ai. The Little Elephant can make one move to choose an arbitrary pair of integers l and r (1 ≤ l ≤ r ≤ n) and increase ai by 1 for all i such that l ≤ i ≤ r.

Help the Little Elephant find the minimum number of moves he needs to convert array a to an arbitrary array sorted in the non-decreasing order. Array a, consisting of n elements, is sorted in the non-decreasing order if for any i (1 ≤ i < n) ai ≤ ai + 1 holds.

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 105) — the size of array a. The next line contains n integers, separated by single spaces — array a (1 ≤ ai ≤ 109). The array elements are listed in the line in the order of their index's increasing.

## Output Format
In a single line print a single integer — the answer to the problem.

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
3
1 2 3
```
```output
0
```
-----
```input
3
3 2 1
```
```output
2
```
-----
```input
4
7 4 1 47
```
```output
6
```

## Note
In the first sample the array is already sorted in the non-decreasing order, so the answer is 0.

In the second sample you need to perform two operations: first increase numbers from second to third (after that the array will be: [3, 3, 2]), and second increase only the last element (the array will be: [3, 3, 3]).

In the third sample you should make at least 6 steps. The possible sequence of the operations is: (2; 3), (2; 3), (2; 3), (3; 3), (3; 3), (3; 3). After that the array converts to [7, 7, 7, 47].

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 called a k-string if it can be represented as k concatenated copies of some string. For example, the string "aabaabaabaab" is at the same time a 1-string, a 2-string and a 4-string, but it is not a 3-string, a 5-string, or a 6-string and so on. Obviously any string is a 1-string.

You are given a string s, consisting of lowercase English letters and a positive integer k. Your task is to reorder the letters in the string s in such a way that the resulting string is a k-string.

## Input Format
The first input line contains integer k (1 ≤ k ≤ 1000). The second line contains s, all characters in s are lowercase English letters. The string length s satisfies the inequality 1 ≤ |s| ≤ 1000, where |s| is the length of string s.

## Output Format
Rearrange the letters in string s in such a way that the result is a k-string. Print the result on a single output line. If there are multiple solutions, print any of them.

If the solution doesn't exist, print "-1" (without quotes).

## Examples
```input
2
aazz
```
```output
azaz
```
-----
```input
3
abcabcabz
```
```output
-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 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 colored stripe is represented by a horizontal row of n square cells, each cell is pained one of k colors. Your task is to repaint the minimum number of cells so that no two neighbouring cells are of the same color. You can use any color from 1 to k to repaint the cells.

## Input Format
The first input line contains two integers n and k (1 ≤ n ≤ 5·105; 2 ≤ k ≤ 26). The second line contains n uppercase English letters. Letter "A" stands for the first color, letter "B" stands for the second color and so on. The first k English letters may be used. Each letter represents the color of the corresponding cell of the stripe.

## Output Format
Print a single integer — the required minimum number of repaintings. In the second line print any possible variant of the repainted stripe.

## Examples
```input
6 3
ABBACC
```
```output
2
ABCACA
```
-----
```input
3 2
BBB
```
```output
1
BAB
```

Now solve the problem and return the code.