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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a permutation $$$p$$$ of length $$$n$$$ (a permutation of length $$$n$$$ is an array of length $$$n$$$ in which each integer from $$$1$$$ to $$$n$$$ occurs exactly once).

You can perform the following operation any number of times (possibly zero):

1. choose two different elements $$$x$$$ and $$$y$$$ and erase them from the permutation;
2. insert the minimum of $$$x$$$ and $$$y$$$ into the permutation in such a way that it becomes the first element;
3. insert the maximum of $$$x$$$ and $$$y$$$ into the permutation in such a way that it becomes the last element.

For example, if $$$p = [1, 5, 4, 2, 3]$$$ and we want to apply the operation to the elements $$$3$$$ and $$$5$$$, then after the first step of the operation, the permutation becomes $$$p = [1, 4, 2]$$$; and after we insert the elements, it becomes $$$p = [3, 1, 4, 2, 5]$$$.

Your task is to calculate the minimum number of operations described above to sort the permutation $$$p$$$ in ascending order (i. e. transform $$$p$$$ so that $$$p_1 < p_2 < \dots < p_n$$$).

## 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 the test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of elements in the permutation.

The second line of the test case contains $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ — the given permutation $$$p$$$.

The sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output a single integer — the minimum number of operations described above to sort the array $$$p$$$ in ascending order.

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

## Note
In the first example, you can proceed as follows:

1. in the permutation $$$p = [1, 5, 4, 2, 3]$$$, let's choose the elements $$$4$$$ and $$$2$$$, then, after applying the operation, the permutation becomes $$$p = [2, 1, 5, 3, 4]$$$;
2. in the permutation $$$p = [2, 1, 5, 3, 4]$$$, let's choose the elements $$$1$$$ and $$$5$$$, then, after applying operation, the permutation becomes $$$p = [1, 2, 3, 4, 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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given $$$n$$$ permutations $$$a_1, a_2, \dots, a_n$$$, each of length $$$m$$$. Recall that a permutation of length $$$m$$$ is a sequence of $$$m$$$ distinct integers from $$$1$$$ to $$$m$$$.

Let the beauty of a permutation $$$p_1, p_2, \dots, p_m$$$ be the largest $$$k$$$ such that $$$p_1 = 1, p_2 = 2, \dots, p_k = k$$$. If $$$p_1 \neq 1$$$, then the beauty is $$$0$$$.

The product of two permutations $$$p \cdot q$$$ is a permutation $$$r$$$ such that $$$r_j = q_{p_j}$$$.

For each $$$i$$$ from $$$1$$$ to $$$n$$$, print the largest beauty of a permutation $$$a_i \cdot a_j$$$ over all $$$j$$$ from $$$1$$$ to $$$n$$$ (possibly, $$$i = j$$$).

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

The first line of each testcase contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 5 \cdot 10^4$$$; $$$1 \le m \le 10$$$) — the number of permutations and the length of each permutation.

The $$$i$$$-th of the next $$$n$$$ lines contains a permutation $$$a_i$$$ — $$$m$$$ distinct integers from $$$1$$$ to $$$m$$$.

The sum of $$$n$$$ doesn't exceed $$$5 \cdot 10^4$$$ over all testcases.

## Output Format
For each testcase, print $$$n$$$ integers. The $$$i$$$-th value should be equal to the largest beauty of a permutation $$$a_i \cdot a_j$$$ over all $$$j$$$ ($$$1 \le j \le n$$$).

## Examples
```input
3
3 4
2 4 1 3
1 2 4 3
2 1 3 4
2 2
1 2
2 1
8 10
3 4 9 6 10 2 7 8 1 5
3 9 1 8 5 7 4 10 2 6
3 10 1 7 5 9 6 4 2 8
1 2 3 4 8 6 10 7 9 5
1 2 3 4 10 6 8 5 7 9
9 6 1 2 10 4 7 8 3 5
7 9 3 2 5 6 4 8 1 10
9 4 3 7 5 6 1 10 8 2
```
```output
1 4 4 
2 2 
10 8 1 6 8 10 1 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 python3.

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:
```python
<your code here>
```

Execution time limit: 5.5 seconds
Memory limit: 512.0 MB

# Problem
The only difference between the easy and the hard version is the constraint on $$$n$$$.

You are given an undirected complete graph on $$$n$$$ vertices. A complete graph is a graph where each pair of vertices is connected by an edge. You have to paint the edges of the graph into two colors, red and blue (each edge will have one color).

A set of vertices $$$S$$$ is red-connected if, for every pair of vertices $$$(v_1, v_2)$$$ such that $$$v_1 \in S$$$ and $$$v_2 \in S$$$, there exists a path from $$$v_1$$$ to $$$v_2$$$ that goes only through red edges and vertices from $$$S$$$. Similarly, a set of vertices $$$S$$$ is blue-connected if, for every pair of vertices $$$(v_1, v_2)$$$ such that $$$v_1 \in S$$$ and $$$v_2 \in S$$$, there exists a path from $$$v_1$$$ to $$$v_2$$$ that goes only through blue edges and vertices from $$$S$$$.

You have to paint the graph in such a way that:

- there is at least one red edge;
- there is at least one blue edge;
- for each set of vertices $$$S$$$ such that $$$|S| \ge 2$$$, $$$S$$$ is either red-connected or blue-connected, but not both.

Calculate the number of ways to paint the graph, and print it modulo $$$998244353$$$.

## Input Format
The first (and only) line contains one integer $$$n$$$ ($$$3 \le n \le 5 \cdot 10^3$$$).

## Output Format
Print one integer — the number of ways to paint the graph, taken modulo $$$998244353$$$.

## Examples
```input
3
```
```output
6
```
-----
```input
4
```
```output
50
```
-----
```input
100
```
```output
878752271
```
-----
```input
1337
```
```output
520628749
```

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 python3.

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:
```python
<your code here>
```

Execution time limit: 5.5 seconds
Memory limit: 512.0 MB

# Problem
The only difference between the easy and the hard version is the constraint on $$$n$$$.

You are given an undirected complete graph on $$$n$$$ vertices. A complete graph is a graph where each pair of vertices is connected by an edge. You have to paint the edges of the graph into two colors, red and blue (each edge will have one color).

A set of vertices $$$S$$$ is red-connected if, for every pair of vertices $$$(v_1, v_2)$$$ such that $$$v_1 \in S$$$ and $$$v_2 \in S$$$, there exists a path from $$$v_1$$$ to $$$v_2$$$ that goes only through red edges and vertices from $$$S$$$. Similarly, a set of vertices $$$S$$$ is blue-connected if, for every pair of vertices $$$(v_1, v_2)$$$ such that $$$v_1 \in S$$$ and $$$v_2 \in S$$$, there exists a path from $$$v_1$$$ to $$$v_2$$$ that goes only through blue edges and vertices from $$$S$$$.

You have to paint the graph in such a way that:

- there is at least one red edge;
- there is at least one blue edge;
- for each set of vertices $$$S$$$ such that $$$|S| \ge 2$$$, $$$S$$$ is either red-connected or blue-connected, but not both.

Calculate the number of ways to paint the graph, and print it modulo $$$998244353$$$.

## Input Format
The first (and only) line contains one integer $$$n$$$ ($$$3 \le n \le 5 \cdot 10^4$$$).

## Output Format
Print one integer — the number of ways to paint the graph, taken modulo $$$998244353$$$.

## Examples
```input
3
```
```output
6
```
-----
```input
4
```
```output
50
```
-----
```input
100
```
```output
878752271
```
-----
```input
1337
```
```output
520628749
```
-----
```input
42013
```
```output
906821221
```

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You have a garland consisting of $$$4$$$ colored light bulbs, the color of the $$$i$$$-th light bulb is $$$s_i$$$.

Initially, all the light bulbs are turned off. Your task is to turn all the light bulbs on. You can perform the following operation any number of times: select a light bulb and switch its state (turn it on if it was off, and turn it off if it was on). The only restriction on the above operation is that you can apply the operation to a light bulb only if the previous operation was applied to a light bulb of a different color (the first operation can be applied to any light bulb).

Calculate the minimum number of operations to turn all the light bulbs on, or report that this is impossible.

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

The single line of each test case contains $$$s$$$ — a sequence of $$$4$$$ characters, where each character is a decimal digit. The $$$i$$$-th character denotes the color of the $$$i$$$-th light bulb.

## Output Format
For each test case, print one integer — the minimum number of operations to turn all the light bulbs on. If it is impossible to turn all the bulbs on, print -1.

## Examples
```input
3
9546
0000
3313
```
```output
4
-1
6
```

## Note
In the first example, all the colors are different, so you can just turn all the bulbs on in $$$4$$$ operations.

In the second example, it is impossible to turn all the bulbs on, because after you switch one light bulb, it is impossible to turn the others on.

In the third example, you can proceed as follows: turn the first light bulb on, turn the third light bulb on, turn the fourth light bulb on, turn the third light bulb off, turn the second light bulb on, turn the third light bulb on.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
For an array $$$a = [a_1, a_2, \dots, a_n]$$$, let's denote its subarray $$$a[l, r]$$$ as the array $$$[a_l, a_{l+1}, \dots, a_r]$$$.

For example, the array $$$a = [1, -3, 1]$$$ has $$$6$$$ non-empty subarrays:

- $$$a[1,1] = [1]$$$;
- $$$a[1,2] = [1,-3]$$$;
- $$$a[1,3] = [1,-3,1]$$$;
- $$$a[2,2] = [-3]$$$;
- $$$a[2,3] = [-3,1]$$$;
- $$$a[3,3] = [1]$$$.

You are given two integers $$$n$$$ and $$$k$$$. Construct an array $$$a$$$ consisting of $$$n$$$ integers such that:

- all elements of $$$a$$$ are from $$$-1000$$$ to $$$1000$$$;
- $$$a$$$ has exactly $$$k$$$ subarrays with positive sums;
- the rest $$$\dfrac{(n+1) \cdot n}{2}-k$$$ subarrays of $$$a$$$ have negative sums.

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

Each test case consists of one line containing two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 30$$$; $$$0 \le k \le \dfrac{(n+1) \cdot n}{2}$$$).

## Output Format
For each test case, print $$$n$$$ integers — the elements of the array meeting the constraints. It can be shown that the answer always exists. If there are multiple answers, print any of them.

## Examples
```input
4
3 2
2 0
2 2
4 6
```
```output
1 -3 1
-13 -42
-13 42
-3 -4 10 -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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a binary string $$$s$$$ consisting of only characters 0 and/or 1.

You can perform several operations on this string (possibly zero). There are two types of operations:

- choose two consecutive elements and swap them. In order to perform this operation, you pay $$$10^{12}$$$ coins;
- choose any element from the string and remove it. In order to perform this operation, you pay $$$10^{12}+1$$$ coins.

Your task is to calculate the minimum number of coins required to sort the string $$$s$$$ in non-decreasing order (i. e. transform $$$s$$$ so that $$$s_1 \le s_2 \le \dots \le s_m$$$, where $$$m$$$ is the length of the string after applying all operations). An empty string is also considered sorted in non-decreasing order.

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

The only line of each test case contains the string $$$s$$$ ($$$1 \le |s| \le 3 \cdot 10^5$$$), consisting of only characters 0 and/or 1.

The sum of lengths of all given strings doesn't exceed $$$3 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the minimum number of coins required to sort the string $$$s$$$ in non-decreasing order.

## Examples
```input
6
100
0
0101
00101101
1001101
11111
```
```output
1000000000001
0
1000000000000
2000000000001
2000000000002
0
```

## Note
In the first example, you have to remove the $$$1$$$-st element, so the string becomes equal to 00.

In the second example, the string is already sorted.

In the third example, you have to swap the $$$2$$$-nd and the $$$3$$$-rd elements, so the string becomes equal to 0011.

In the fourth example, you have to swap the $$$3$$$-rd and the $$$4$$$-th elements, so the string becomes equal to 00011101, and then remove the $$$7$$$-th element, so the string becomes equal to 0001111.

In the fifth example, you have to remove the $$$1$$$-st element, so the string becomes equal to 001101, and then remove the $$$5$$$-th element, so the string becomes equal to 00111.

In the sixth example, the string is already sorted.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 512.0 MB

# Problem
Consider a tournament with $$$n$$$ participants. The rating of the $$$i$$$-th participant is $$$a_i$$$.

The tournament will be organized as follows. First of all, organizers will assign each participant an index from $$$1$$$ to $$$n$$$. All indices will be unique. Let $$$p_i$$$ be the participant who gets the index $$$i$$$.

Then, $$$n-1$$$ games will be held. In the first game, participants $$$p_1$$$ and $$$p_2$$$ will play. In the second game, the winner of the first game will play against $$$p_3$$$. In the third game, the winner of the second game will play against $$$p_4$$$, and so on — in the last game, the winner of the $$$(n-2)$$$-th game will play against $$$p_n$$$.

Monocarp wants to predict the results of all $$$n-1$$$ games (of course, he will do the prediction only after the indices of the participants are assigned). He knows for sure that, when two participants with ratings $$$x$$$ and $$$y$$$ play, and $$$|x - y| > k$$$, the participant with the higher rating wins. But if $$$|x - y| \le k$$$, any of the two participants may win.

Among all $$$n!$$$ ways to assign the indices to participants, calculate the number of ways to do this so that Monocarp can predict the results of all $$$n-1$$$ games. Since the answer can be large, print it modulo $$$998244353$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^6$$$; $$$0 \le k \le 10^9$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_1 \le a_2 \le \dots \le a_n \le 10^9$$$).

## Output Format
Print one integer — the number of ways to assign the indices to the participants so that Monocarp can predict the results of all $$$n-1$$$ games.

## Examples
```input
4 3
7 12 17 21
```
```output
24
```
-----
```input
3 7
4 9 28
```
```output
4
```
-----
```input
4 1
1 2 3 4
```
```output
0
```
-----
```input
4 1
1 2 2 4
```
```output
12
```
-----
```input
16 30
8 12 15 27 39 44 49 50 51 53 58 58 59 67 68 100
```
```output
527461297
```

## Note
In the first example, a match with any pair of players can be predicted by Monocarp, so all $$$24$$$ ways to assign indices should be counted.

In the second example, suitable ways are $$$[1, 3, 2]$$$, $$$[2, 3, 1]$$$, $$$[3, 1, 2$$$] and $$$[3, 2, 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 python3.

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:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Conveyor matrix $$$m_n$$$ is matrix of size $$$n \times n$$$, where $$$n$$$ is an even number. The matrix consists of concentric ribbons moving clockwise.

In other words, the conveyor matrix for $$$n = 2$$$ is simply a matrix $$$2 \times 2$$$, whose cells form a cycle of length $$$4$$$ clockwise. For any natural $$$k \ge 2$$$, the matrix $$$m_{2k}$$$ is obtained by adding to the matrix $$$m_{2k - 2}$$$ an outer layer forming a clockwise cycle.

The conveyor matrix $$$8 \times 8$$$.

You are standing in a cell with coordinates $$$x_1, y_1$$$ and you want to get into a cell with coordinates $$$x_2, y_2$$$. A cell has coordinates $$$x, y$$$ if it is located at the intersection of the $$$x$$$th row and the $$$y$$$th column.

Standing on some cell, every second you will move to the cell next in the direction of movement of the tape on which you are. You can also move to a neighboring cell by spending one unit of energy. Movements happen instantly and you can make an unlimited number of them at any time.

Your task is to find the minimum amount of energy that will have to be spent to get from the cell with coordinates $$$x_1, y_1$$$ to the cell with coordinates $$$x_2, y_2$$$.

For example, $$$n=8$$$ initially you are in a cell with coordinates $$$1,3$$$ and you want to get into a cell with coordinates $$$6, 4$$$. You can immediately make $$$2$$$ movements, once you are in a cell with coordinates $$$3, 3$$$, and then after $$$8$$$ seconds you will be in the right cell.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — the number of test cases.

The descriptions of the test cases follow.

The description of each test case consists of one string containing five integers $$$n$$$, $$$x_1$$$, $$$y_1$$$, $$$x_2$$$ and $$$y_2$$$ ($$$1 \le x_1, y_1, x_2, y_2 \le n \le 10^9$$$) — matrix size and the coordinates of the start and end cells. It is guaranteed that the number $$$n$$$ is even.

## Output Format
For each test case, print one integer in a separate line — the minimum amount of energy that will have to be spent to get from the cell with coordinates $$$x_1, y_1$$$ to the cell with coordinates $$$x_2, y_2$$$.

## Examples
```input
5
2 1 1 2 2
4 1 4 3 3
8 1 3 4 6
100 10 20 50 100
1000000000 123456789 987654321 998244353 500000004
```
```output
0
1
2
9
10590032
```

Now solve the problem and return the code.