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
oolimry has an array $$$a$$$ of length $$$n$$$ which he really likes. Today, you have changed his array to $$$b$$$, a permutation of $$$a$$$, to make him sad.

Because oolimry is only a duck, he can only perform the following operation to restore his array:

- Choose two integers $$$i,j$$$ such that $$$1 \leq i,j \leq n$$$.
- Swap $$$b_i$$$ and $$$b_j$$$.

The sadness of the array $$$b$$$ is the minimum number of operations needed to transform $$$b$$$ into $$$a$$$.

Given the array $$$a$$$, find any array $$$b$$$ which is a permutation of $$$a$$$ that has the maximum sadness over all permutations of the array $$$a$$$.

## Input Format
Each test contains multiple test cases. The first line contains a single 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 a single 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, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$)  — elements of the array $$$a$$$.

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 $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ — describing the array $$$b$$$. If there are multiple answers, you may print any.

## Examples
```input
2
2
2 1
4
1 2 3 3
```
```output
1 2
3 3 2 1
```

## Note
In the first test case, the array $$$[1,2]$$$ has sadness $$$1$$$. We can transform $$$[1,2]$$$ into $$$[2,1]$$$ using one operation with $$$(i,j)=(1,2)$$$.

In the second test case, the array $$$[3,3,2,1]$$$ has sadness $$$2$$$. We can transform $$$[3,3,2,1]$$$ into $$$[1,2,3,3]$$$ with two operations with $$$(i,j)=(1,4)$$$ and $$$(i,j)=(2,3)$$$ respectively.

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
oolimry has an array $$$a$$$ of length $$$n$$$ which he really likes. Today, you have changed his array to $$$b$$$, a permutation of $$$a$$$, to make him sad.

Because oolimry is only a duck, he can only perform the following operation to restore his array:

- Choose two integers $$$i,j$$$ such that $$$1 \leq i,j \leq n$$$.
- Swap $$$b_i$$$ and $$$b_j$$$.

The sadness of the array $$$b$$$ is the minimum number of operations needed to transform $$$b$$$ into $$$a$$$.

Given the arrays $$$a$$$ and $$$b$$$, where $$$b$$$ is a permutation of $$$a$$$, determine if $$$b$$$ has the maximum sadness over all permutations of $$$a$$$.

## Input Format
Each test contains multiple test cases. The first line contains a single 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 a single 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, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$)  — the elements of the array $$$a$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq n$$$)  — the elements of the array $$$b$$$.

It is guaranteed that $$$b$$$ is a permutation of $$$a$$$.

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 "AC" (without quotes) if $$$b$$$ has the maximum sadness over all permutations of $$$a$$$, and "WA" (without quotes) otherwise.

## Examples
```input
4
2
2 1
1 2
4
1 2 3 3
3 3 2 1
2
2 1
2 1
4
1 2 3 3
3 2 3 1
```
```output
AC
AC
WA
WA
```

## Note
In the first test case, the array $$$[1,2]$$$ has sadness $$$1$$$. We can transform $$$[1,2]$$$ into $$$[2,1]$$$ using one operation with $$$(i,j)=(1,2)$$$.

In the second test case, the array $$$[3,3,2,1]$$$ has sadness $$$2$$$. We can transform $$$[3,3,2,1]$$$ into $$$[1,2,3,3]$$$ with two operations with $$$(i,j)=(1,4)$$$ and $$$(i,j)=(2,3)$$$ respectively.

In the third test case, the array $$$[2,1]$$$ has sadness $$$0$$$.

In the fourth test case, the array $$$[3,2,3,1]$$$ has sadness $$$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
There is a grid with $$$r$$$ rows and $$$c$$$ columns, where the square on the $$$i$$$-th row and $$$j$$$-th column has an integer $$$a_{i, j}$$$ written on it. Initially, all elements are set to $$$0$$$. We are allowed to do the following operation:

- Choose indices $$$1 \le i \le r$$$ and $$$1 \le j \le c$$$, then replace all values on the same row or column as $$$(i, j)$$$ with the value xor $$$1$$$. In other words, for all $$$a_{x, y}$$$ where $$$x=i$$$ or $$$y=j$$$ or both, replace $$$a_{x, y}$$$ with $$$a_{x, y}$$$ xor $$$1$$$.

You want to form grid $$$b$$$ by doing the above operations a finite number of times. However, some elements of $$$b$$$ are missing and are replaced with '?' instead.

Let $$$k$$$ be the number of '?' characters. Among all the $$$2^k$$$ ways of filling up the grid $$$b$$$ by replacing each '?' with '0' or '1', count the number of grids, that can be formed by doing the above operation a finite number of times, starting from the grid filled with $$$0$$$. As this number can be large, output it modulo $$$998244353$$$.

## Input Format
The first line contains two integers $$$r$$$ and $$$c$$$ ($$$1 \le r, c \le 2000$$$)  — the number of rows and columns of the grid respectively.

The $$$i$$$-th of the next $$$r$$$ lines contain $$$c$$$ characters $$$b_{i, 1}, b_{i, 2}, \ldots, b_{i, c}$$$ ($$$b_{i, j} \in \{0, 1, ?\}$$$).

## Output Format
Print a single integer representing the number of ways to fill up grid $$$b$$$ modulo $$$998244353$$$.

## Examples
```input
3 3
?10
1??
010
```
```output
1
```
-----
```input
2 3
000
001
```
```output
0
```
-----
```input
1 1
?
```
```output
2
```
-----
```input
6 9
1101011?0
001101?00
101000110
001011010
0101?01??
00?1000?0
```
```output
8
```

## Note
In the first test case, the only way to fill in the $$$\texttt{?}$$$s is to fill it in as such:

010111010

This can be accomplished by doing a single operation by choosing $$$(i,j)=(2,2)$$$.

In the second test case, it can be shown that there is no sequence of operations that can produce that grid.

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 have a binary string $$$a$$$ of length $$$n$$$ consisting only of digits $$$0$$$ and $$$1$$$.

You are given $$$q$$$ queries. In the $$$i$$$-th query, you are given two indices $$$l$$$ and $$$r$$$ such that $$$1 \le l \le r \le n$$$.

Let $$$s=a[l,r]$$$. You are allowed to do the following operation on $$$s$$$:

1. Choose two indices $$$x$$$ and $$$y$$$ such that $$$1 \le x \le y \le |s|$$$. Let $$$t$$$ be the substring $$$t = s[x, y]$$$. Then for all $$$1 \le i \le |t| - 1$$$, the condition $$$t_i \neq t_{i+1}$$$ has to hold. Note that $$$x = y$$$ is always a valid substring.
2. Delete the substring $$$s[x, y]$$$ from $$$s$$$.

For each of the $$$q$$$ queries, find the minimum number of operations needed to make $$$s$$$ an empty string.

Note that for a string $$$s$$$, $$$s[l,r]$$$ denotes the subsegment $$$s_l,s_{l+1},\ldots,s_r$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10 ^ 5$$$)  — the length of the binary string $$$a$$$ and the number of queries respectively.

The second line contains a binary string $$$a$$$ of length $$$n$$$ ($$$a_i \in \{0, 1\}$$$).

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$)  — representing the substring of each query.

## Output Format
Print $$$q$$$ lines, the $$$i$$$-th line representing the minimum number of operations needed for the $$$i$$$-th query.

## Examples
```input
5 3
11011
2 4
1 5
3 5
```
```output
1
3
2
```
-----
```input
10 3
1001110110
1 10
2 5
5 10
```
```output
4
2
3
```

## Note
In the first test case,

1. The substring is $$$\texttt{101}$$$, so we can do one operation to make the substring empty.
2. The substring is $$$\texttt{11011}$$$, so we can do one operation on $$$s[2, 4]$$$ to make $$$\texttt{11}$$$, then use two more operations to make the substring empty.
3. The substring is $$$\texttt{011}$$$, so we can do one operation on $$$s[1, 2]$$$ to make $$$\texttt{1}$$$, then use one more operation to make the substring empty.

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: 5.0 seconds
Memory limit: 1024.0 MB

# Problem
You have a permutation $$$p$$$ of integers from $$$1$$$ to $$$n$$$.

You have a strength of $$$s$$$ and will perform the following operation some times:

- Choose an index $$$i$$$ such that $$$1 \leq i \leq |p|$$$ and $$$|i-p_i| \leq s$$$.
- For all $$$j$$$ such that $$$1 \leq j \leq |p|$$$ and $$$p_i<p_j$$$, update $$$p_j$$$ to $$$p_j-1$$$.
- Delete the $$$i$$$-th element from $$$p$$$. Formally, update $$$p$$$ to $$$[p_1,\ldots,p_{i-1},p_{i+1},\ldots,p_n]$$$.

It can be shown that no matter what $$$i$$$ you have chosen, $$$p$$$ will be a permutation of integers from $$$1$$$ to $$$|p|$$$ after all operations.

You want to be able to transform $$$p$$$ into the empty permutation. Find the minimum strength $$$s$$$ that will allow you to do so.

## Input Format
The first line of input contains a single integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$)  — the length of the permutation $$$p$$$.

The second line of input conatains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$)  — the elements of the permutation $$$p$$$.

It is guaranteed that all elements in $$$p$$$ are distinct.

## Output Format
Print the minimum strength $$$s$$$ required.

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

## Note
In the first test case, the minimum $$$s$$$ required is $$$1$$$.

Here is how we can transform $$$p$$$ into the empty permutation with $$$s=1$$$:

- In the first move, you can only choose $$$i=2$$$ as choosing any other value of $$$i$$$ will result in $$$|i-p_i| \leq s$$$ being false. With $$$i=2$$$, $$$p$$$ will be changed to $$$[2,1]$$$.
- In the second move, you choose $$$i=1$$$, then $$$p$$$ will be changed to $$$[1]$$$.
- In the third move, you choose $$$i=1$$$, then $$$p$$$ will be changed to $$$[~]$$$.

It can be shown that with $$$s=0$$$, it is impossible to transform $$$p$$$ into the empty 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
Tokitsukaze has a sequence $$$a$$$ of length $$$n$$$. For each operation, she selects two numbers $$$a_i$$$ and $$$a_j$$$ ($$$i \ne j$$$; $$$1 \leq i,j \leq n$$$).

- If $$$a_i = a_j$$$, change one of them to $$$0$$$.
- Otherwise change both of them to $$$\min(a_i, a_j)$$$.

Tokitsukaze wants to know the minimum number of operations to change all numbers in the sequence to $$$0$$$. It can be proved that the answer always exists.

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

For each test case, the first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 100$$$) — the length of the sequence $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 100$$$) — the sequence $$$a$$$.

## Output Format
For each test case, print a single integer — the minimum number of operations to change all numbers in the sequence to $$$0$$$.

## Examples
```input
3
3
1 2 3
3
1 2 2
3
1 2 0
```
```output
4
3
2
```

## Note
In the first test case, one of the possible ways to change all numbers in the sequence to $$$0$$$:

In the $$$1$$$-st operation, $$$a_1 < a_2$$$, after the operation, $$$a_2 = a_1 = 1$$$. Now the sequence $$$a$$$ is $$$[1,1,3]$$$.

In the $$$2$$$-nd operation, $$$a_1 = a_2 = 1$$$, after the operation, $$$a_1 = 0$$$. Now the sequence $$$a$$$ is $$$[0,1,3]$$$.

In the $$$3$$$-rd operation, $$$a_1 < a_2$$$, after the operation, $$$a_2 = 0$$$. Now the sequence $$$a$$$ is $$$[0,0,3]$$$.

In the $$$4$$$-th operation, $$$a_2 < a_3$$$, after the operation, $$$a_3 = 0$$$. Now the sequence $$$a$$$ is $$$[0,0,0]$$$.

So the minimum number of operations is $$$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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
This is the easy version of the problem. The only difference between the two versions is that the harder version asks additionally for a minimum number of subsegments.

Tokitsukaze has a binary string $$$s$$$ of length $$$n$$$, consisting only of zeros and ones, $$$n$$$ is even.

Now Tokitsukaze divides $$$s$$$ into the minimum number of contiguous subsegments, and for each subsegment, all bits in each subsegment are the same. After that, $$$s$$$ is considered good if the lengths of all subsegments are even.

For example, if $$$s$$$ is "11001111", it will be divided into "11", "00" and "1111". Their lengths are $$$2$$$, $$$2$$$, $$$4$$$ respectively, which are all even numbers, so "11001111" is good. Another example, if $$$s$$$ is "1110011000", it will be divided into "111", "00", "11" and "000", and their lengths are $$$3$$$, $$$2$$$, $$$2$$$, $$$3$$$. Obviously, "1110011000" is not good.

Tokitsukaze wants to make $$$s$$$ good by changing the values of some positions in $$$s$$$. Specifically, she can perform the operation any number of times: change the value of $$$s_i$$$ to '0' or '1'($$$1 \leq i \leq n$$$). Can you tell her the minimum number of operations to make $$$s$$$ good?

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

For each test case, the first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the length of $$$s$$$, it is guaranteed that $$$n$$$ is even.

The second line contains a binary string $$$s$$$ of length $$$n$$$, consisting only of zeros and ones.

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 line with one integer — the minimum number of operations to make $$$s$$$ good.

## Examples
```input
5
10
1110011000
8
11001111
2
00
2
11
6
100110
```
```output
3
0
0
0
3
```

## Note
In the first test case, one of the ways to make $$$s$$$ good is the following.

Change $$$s_3$$$, $$$s_6$$$ and $$$s_7$$$ to '0', after that $$$s$$$ becomes "1100000000", it can be divided into "11" and "00000000", which lengths are $$$2$$$ and $$$8$$$ respectively. There are other ways to operate $$$3$$$ times to make $$$s$$$ good, such as "1111110000", "1100001100", "1111001100".

In the second, third and fourth test cases, $$$s$$$ is good initially, so no operation is required.

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
Given a sequence $$$a_1, a_2, \ldots, a_n$$$, find the minimum number of elements to remove from the sequence such that after the removal, the sum of every $$$2$$$ consecutive elements is even.

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

The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 10^5$$$).

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

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

## Output Format
For each test case, print a single integer — the minimum number of elements to remove from the sequence such that the sum of every $$$2$$$ consecutive elements is even.

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

## Note
In the first test case, after removing $$$3$$$, the sequence becomes $$$[2,4,6,8]$$$. The pairs of consecutive elements are $$$\{[2, 4], [4, 6], [6, 8]\}$$$. Each consecutive pair has an even sum now. Hence, we only need to remove $$$1$$$ element to satisfy the condition asked.

In the second test case, each consecutive pair already has an even sum so we need not remove any element.

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 binary string $$$s$$$ of length $$$n$$$.

Let's define $$$d_i$$$ as the number whose decimal representation is $$$s_i s_{i+1}$$$ (possibly, with a leading zero). We define $$$f(s)$$$ to be the sum of all the valid $$$d_i$$$. In other words, $$$f(s) = \sum\limits_{i=1}^{n-1} d_i$$$.

For example, for the string $$$s = 1011$$$:

- $$$d_1 = 10$$$ (ten);
- $$$d_2 = 01$$$ (one)
- $$$d_3 = 11$$$ (eleven);
- $$$f(s) = 10 + 01 + 11 = 22$$$.

In one operation you can swap any two adjacent elements of the string. Find the minimum value of $$$f(s)$$$ that can be achieved if at most $$$k$$$ operations are allowed.

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

First line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$0 \le k \le 10^9$$$) — the length of the string and the maximum number of operations allowed.

The second line of each test case contains the binary string $$$s$$$ of length $$$n$$$, consisting of only zeros and ones.

It is also given that sum of $$$n$$$ over all the test cases doesn't exceed $$$10^5$$$.

## Output Format
For each test case, print the minimum value of $$$f(s)$$$ you can obtain with at most $$$k$$$ operations.

## Examples
```input
3
4 0
1010
7 1
0010100
5 2
00110
```
```output
21
22
12
```

## Note
- For the first example, you can't do any operation so the optimal string is $$$s$$$ itself. $$$f(s) = f(1010) = 10 + 01 + 10 = 21$$$.
- For the second example, one of the optimal strings you can obtain is "0011000". The string has an $$$f$$$ value of $$$22$$$.
- For the third example, one of the optimal strings you can obtain is "00011". The string has an $$$f$$$ value of $$$12$$$.

Now solve the problem and return the code.