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 a given an array $$$a$$$ of length $$$n$$$. Find a subarray $$$a[l..r]$$$ with length at least $$$k$$$ with the largest median.

A median in an array of length $$$n$$$ is an element which occupies position number $$$\lfloor \frac{n + 1}{2} \rfloor$$$ after we sort the elements in non-decreasing order. For example: $$$median([1, 2, 3, 4]) = 2$$$, $$$median([3, 2, 1]) = 2$$$, $$$median([2, 1, 2, 1]) = 1$$$.

Subarray $$$a[l..r]$$$ is a contiguous part of the array $$$a$$$, i. e. the array $$$a_l,a_{l+1},\ldots,a_r$$$ for some $$$1 \leq l \leq r \leq n$$$, its length is $$$r - l + 1$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$).

## Output Format
Output one integer $$$m$$$ — the maximum median you can get.

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

## Note
In the first example all the possible subarrays are $$$[1..3]$$$, $$$[1..4]$$$, $$$[1..5]$$$, $$$[2..4]$$$, $$$[2..5]$$$ and $$$[3..5]$$$ and the median for all of them is $$$2$$$, so the maximum possible median is $$$2$$$ too.

In the second example $$$median([3..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 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
There are $$$n$$$ cities and $$$m$$$ bidirectional roads in the country. The roads in the country form an undirected weighted graph. The graph is not guaranteed to be connected. Each road has it's own parameter $$$w$$$. You can travel through the roads, but the government made a new law: you can only go through two roads at a time (go from city $$$a$$$ to city $$$b$$$ and then from city $$$b$$$ to city $$$c$$$) and you will have to pay $$$(w_{ab} + w_{bc})^2$$$ money to go through those roads. Find out whether it is possible to travel from city $$$1$$$ to every other city $$$t$$$ and what's the minimum amount of money you need to get from $$$1$$$ to $$$t$$$.

## Input Format
First line contains two integers $$$n$$$, $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq m \leq min(\frac{n \cdot (n - 1)}{2}, 2 \cdot 10^5)$$$).

Next $$$m$$$ lines each contain three integers $$$v_i$$$, $$$u_i$$$, $$$w_i$$$ ($$$1 \leq v_i, u_i \leq n$$$, $$$1 \leq w_i \leq 50$$$, $$$u_i \neq v_i$$$). It's guaranteed that there are no multiple edges, i.e. for any edge $$$(u_i, v_i)$$$ there are no other edges $$$(u_i, v_i)$$$ or $$$(v_i, u_i)$$$.

## Output Format
For every city $$$t$$$ print one integer. If there is no correct path between $$$1$$$ and $$$t$$$ output $$$-1$$$. Otherwise print out the minimum amount of money needed to travel from $$$1$$$ to $$$t$$$.

## Examples
```input
5 6
1 2 3
2 3 4
3 4 5
4 5 6
1 5 1
2 4 2
```
```output
0 98 49 25 114
```
-----
```input
3 2
1 2 1
2 3 2
```
```output
0 -1 9
```

## Note
The graph in the first example looks like this.

In the second example the path from $$$1$$$ to $$$3$$$ goes through $$$2$$$, so the resulting payment is $$$(1 + 2)^2 = 9$$$.

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

# Problem
You are given a tree consisting of $$$n$$$ vertices, and $$$m$$$ simple vertex paths. Your task is to find how many pairs of those paths intersect at exactly one vertex. More formally you have to find the number of pairs $$$(i, j)$$$ $$$(1 \leq i < j \leq m)$$$ such that $$$path_i$$$ and $$$path_j$$$ have exactly one vertex in common.

## Input Format
First line contains a single integer $$$n$$$ $$$(1 \leq n \leq 3 \cdot 10^5)$$$.

Next $$$n - 1$$$ lines describe the tree. Each line contains two integers $$$u$$$ and $$$v$$$ $$$(1 \leq u, v \leq n)$$$ describing an edge between vertices $$$u$$$ and $$$v$$$.

Next line contains a single integer $$$m$$$ $$$(1 \leq m \leq 3 \cdot 10^5)$$$.

Next $$$m$$$ lines describe paths. Each line describes a path by it's two endpoints $$$u$$$ and $$$v$$$ $$$(1 \leq u, v \leq n)$$$. The given path is all the vertices on the shortest path from $$$u$$$ to $$$v$$$ (including $$$u$$$ and $$$v$$$).

## Output Format
Output a single integer — the number of pairs of paths that intersect at exactly one vertex.

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

## Note
The tree in the first example and paths look like this. Pairs $$$(1,4)$$$ and $$$(3,4)$$$ intersect at one vertex.

In the second example all three paths contain the same single vertex, so all pairs $$$(1, 2)$$$, $$$(1, 3)$$$ and $$$(2, 3)$$$ intersect at one vertex.

The third example is the same as the first example with two additional paths. Pairs $$$(1,4)$$$, $$$(1,5)$$$, $$$(2,5)$$$, $$$(3,4)$$$, $$$(3,5)$$$, $$$(3,6)$$$ and $$$(5,6)$$$ intersect at one vertex.

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

# Problem
A sequence of $$$n$$$ integers is called a permutation if it contains all integers from $$$1$$$ to $$$n$$$ exactly once.

Given two integers $$$n$$$ and $$$k$$$, construct a permutation $$$a$$$ of numbers from $$$1$$$ to $$$n$$$ which has exactly $$$k$$$ peaks. An index $$$i$$$ of an array $$$a$$$ of size $$$n$$$ is said to be a peak if $$$1 < i < n$$$ and $$$a_i \gt a_{i-1}$$$ and $$$a_i \gt a_{i+1}$$$. If such permutation is not possible, then print $$$-1$$$.

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

Then $$$t$$$ lines follow, each containing two space-separated integers $$$n$$$ ($$$1 \leq n \leq 100$$$) and $$$k$$$ ($$$0 \leq k \leq n$$$) — the length of an array and the required number of peaks.

## Output Format
Output $$$t$$$ lines. For each test case, if there is no permutation with given length and number of peaks, then print $$$-1$$$. Otherwise print a line containing $$$n$$$ space-separated integers which forms a permutation of numbers from $$$1$$$ to $$$n$$$ and contains exactly $$$k$$$ peaks.

If there are multiple answers, print any.

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

## Note
In the second test case of the example, we have array $$$a = [2,4,1,5,3]$$$. Here, indices $$$i=2$$$ and $$$i=4$$$ are the peaks of the array. This is because $$$(a_{2} \gt a_{1} $$$, $$$a_{2} \gt a_{3})$$$ and $$$(a_{4} \gt a_{3}$$$, $$$a_{4} \gt a_{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
A sequence of $$$n$$$ non-negative integers ($$$n \ge 2$$$) $$$a_1, a_2, \dots, a_n$$$ is called good if for all $$$i$$$ from $$$1$$$ to $$$n-1$$$ the following condition holds true: $$$$$$a_1 \: \& \: a_2 \: \& \: \dots \: \& \: a_i = a_{i+1} \: \& \: a_{i+2} \: \& \: \dots \: \& \: a_n,$$$$$$ where $$$\&$$$ denotes the bitwise AND operation.

You are given an array $$$a$$$ of size $$$n$$$ ($$$n \geq 2$$$). Find the number of permutations $$$p$$$ of numbers ranging from $$$1$$$ to $$$n$$$, for which the sequence $$$a_{p_1}$$$, $$$a_{p_2}$$$, ... ,$$$a_{p_n}$$$ is good. Since this number can be large, output it modulo $$$10^9+7$$$.

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

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

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

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

## Output Format
Output $$$t$$$ lines, where the $$$i$$$-th line contains the number of good permutations in the $$$i$$$-th test case modulo $$$10^9 + 7$$$.

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

## Note
In the first test case, since all the numbers are equal, whatever permutation we take, the sequence is good. There are a total of $$$6$$$ permutations possible with numbers from $$$1$$$ to $$$3$$$: $$$[1,2,3]$$$, $$$[1,3,2]$$$, $$$[2,1,3]$$$, $$$[2,3,1]$$$, $$$[3,1,2]$$$, $$$[3,2,1]$$$.

In the second test case, it can be proved that no permutation exists for which the sequence is good.

In the third test case, there are a total of $$$36$$$ permutations for which the sequence is good. One of them is the permutation $$$[1,5,4,2,3]$$$ which results in the sequence $$$s=[0,0,3,2,0]$$$. This is a good sequence because

- $$$ s_1 = s_2 \: \& \: s_3 \: \& \: s_4 \: \& \: s_5 = 0$$$,
- $$$ s_1 \: \& \: s_2 = s_3 \: \& \: s_4 \: \& \: s_5 = 0$$$,
- $$$ s_1 \: \& \: s_2 \: \& \: s_3 = s_4 \: \& \: s_5 = 0$$$,
- $$$ s_1 \: \& \: s_2 \: \& \: s_3 \: \& \: s_4 = s_5 = 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 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an integer $$$n$$$. You have to apply $$$m$$$ operations to it.

In a single operation, you must replace every digit $$$d$$$ of the number with the decimal representation of integer $$$d + 1$$$. For example, $$$1912$$$ becomes $$$21023$$$ after applying the operation once.

You have to find the length of $$$n$$$ after applying $$$m$$$ operations. Since the answer can be very large, print it modulo $$$10^9+7$$$.

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

The only line of each test case contains two integers $$$n$$$ ($$$1 \le n \le 10^9$$$) and $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — the initial number and the number of operations.

## Output Format
For each test case output the length of the resulting number modulo $$$10^9+7$$$.

## Examples
```input
5
1912 1
5 6
999 1
88 2
12 100
```
```output
5
2
6
4
2115
```

## Note
For the first test, $$$1912$$$ becomes $$$21023$$$ after $$$1$$$ operation which is of length $$$5$$$.

For the second test, $$$5$$$ becomes $$$21$$$ after $$$6$$$ operations which is of length $$$2$$$.

For the third test, $$$999$$$ becomes $$$101010$$$ after $$$1$$$ operation which is of length $$$6$$$.

For the fourth test, $$$88$$$ becomes $$$1010$$$ after $$$2$$$ operations which is of length $$$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 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 an array $$$a$$$ of $$$n$$$ ($$$n \geq 2$$$) positive integers and an integer $$$p$$$. Consider an undirected weighted graph of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$ for which the edges between the vertices $$$i$$$ and $$$j$$$ ($$$i<j$$$) are added in the following manner:

- If $$$gcd(a_i, a_{i+1}, a_{i+2}, \dots, a_{j}) = min(a_i, a_{i+1}, a_{i+2}, \dots, a_j)$$$, then there is an edge of weight $$$min(a_i, a_{i+1}, a_{i+2}, \dots, a_j)$$$ between $$$i$$$ and $$$j$$$.
- If $$$i+1=j$$$, then there is an edge of weight $$$p$$$ between $$$i$$$ and $$$j$$$.

Here $$$gcd(x, y, \ldots)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$, $$$y$$$, ....

Note that there could be multiple edges between $$$i$$$ and $$$j$$$ if both of the above conditions are true, and if both the conditions fail for $$$i$$$ and $$$j$$$, then there is no edge between these vertices.

The goal is to find the weight of the minimum spanning tree of this graph.

## 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 two integers $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) and $$$p$$$ ($$$1 \leq p \leq 10^9$$$) — the number of nodes and the parameter $$$p$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

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

## Output Format
Output $$$t$$$ lines. For each test case print the weight of the corresponding graph.

## Examples
```input
4
2 5
10 10
2 5
3 3
4 5
5 2 4 9
8 8
5 3 3 6 10 100 9 15
```
```output
5
3
12
46
```

## Note
Here are the graphs for the four test cases of the example (the edges of a possible MST of the graphs are marked pink):

For test case 1

For test case 2

For test case 3

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

# Problem
An array is called beautiful if all the elements in the array are equal.

You can transform an array using the following steps any number of times:

1. Choose two indices $$$i$$$ and $$$j$$$ ($$$1 \leq i,j \leq n$$$), and an integer $$$x$$$ ($$$1 \leq x \leq a_i$$$). Let $$$i$$$ be the source index and $$$j$$$ be the sink index.
2. Decrease the $$$i$$$-th element by $$$x$$$, and increase the $$$j$$$-th element by $$$x$$$. The resulting values at $$$i$$$-th and $$$j$$$-th index are $$$a_i-x$$$ and $$$a_j+x$$$ respectively.
3. The cost of this operation is $$$x \cdot |j-i| $$$.
4. Now the $$$i$$$-th index can no longer be the sink and the $$$j$$$-th index can no longer be the source.

For example, array $$$[0, 2, 3, 3]$$$ can be transformed into a beautiful array $$$[2, 2, 2, 2]$$$ with total cost $$$1 \cdot |1-3| + 1 \cdot |1-4| = 5$$$.

An array is called balanced, if it can be transformed into a beautiful array, and the cost of such transformation is uniquely defined. In other words, the minimum cost of transformation into a beautiful array equals the maximum cost.

You are given an array $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$, consisting of non-negative integers. Your task is to find the number of balanced arrays which are permutations of the given array. Two arrays are considered different, if elements at some position differ. Since the answer can be large, output it modulo $$$10^9 + 7$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the size of the array.

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

## Output Format
Output a single integer — the number of balanced permutations modulo $$$10^9+7$$$.

## Examples
```input
3
1 2 3
```
```output
6
```
-----
```input
4
0 4 0 4
```
```output
2
```
-----
```input
5
0 11 12 13 14
```
```output
120
```

## Note
In the first example, $$$[1, 2, 3]$$$ is a valid permutation as we can consider the index with value $$$3$$$ as the source and index with value $$$1$$$ as the sink. Thus, after conversion we get a beautiful array $$$[2, 2, 2]$$$, and the total cost would be $$$2$$$. We can show that this is the only transformation of this array that leads to a beautiful array. Similarly, we can check for other permutations too.

In the second example, $$$[0, 0, 4, 4]$$$ and $$$[4, 4, 0, 0]$$$ are balanced permutations.

In the third example, all permutations are balanced.

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
You are given 2 arrays $$$a$$$ and $$$b$$$, both of size $$$n$$$. You can swap two elements in $$$b$$$ at most once (or leave it as it is), and you are required to minimize the value $$$$$$\sum_{i}|a_{i}-b_{i}|.$$$$$$

Find the minimum possible value of this sum.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le {10^9}$$$).

The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le {10^9}$$$).

## Output Format
Output the minimum value of $$$\sum_{i}|a_{i}-b_{i}|$$$.

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

## Note
In the first example, we can swap the first and fifth element in array $$$b$$$, so that it becomes $$$[ 5, 2, 3, 4, 1 ]$$$.

Therefore, the minimum possible value of this sum would be $$$|5-5| + |4-2| + |3-3| + |2-4| + |1-1| = 4$$$.

In the second example, we can swap the first and second elements. So, our answer would be $$$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: 5.0 seconds
Memory limit: 512.0 MB

# Problem
You were playing with permutation $$$p$$$ of length $$$n$$$, but you lost it in Blair, Alabama!

Luckily, you remember some information about the permutation. More specifically, you remember an array $$$b$$$ of length $$$n$$$, where $$$b_i$$$ is the number of indices $$$j$$$ such that $$$j < i$$$ and $$$p_j > p_i$$$.

You have the array $$$b$$$, and you want to find the permutation $$$p$$$. However, your memory isn't perfect, and you constantly change the values of $$$b$$$ as you learn more. For the next $$$q$$$ seconds, one of the following things happen:

1. $$$1$$$ $$$i$$$ $$$x$$$ — you realize that $$$b_i$$$ is equal to $$$x$$$;
2. $$$2$$$ $$$i$$$ — you need to find the value of $$$p_i$$$. If there's more than one answer, print any. It can be proven that there's always at least one possible answer under the constraints of the problem.

Answer the queries, so you can remember the array!

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

The second line contains $$$n$$$ integers $$$b_1, b_2 \ldots, b_n$$$ ($$$0 \leq b_i < i$$$) — your initial memory of the array $$$b$$$.

The third line contains a single integer $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — the number of queries.

The next $$$q$$$ lines contain the queries, each with one of the following formats:

- $$$1$$$ $$$i$$$ $$$x$$$ ($$$0 \leq x < i \leq n$$$), representing a query of type $$$1$$$.
- $$$2$$$ $$$i$$$ ($$$1 \leq i \leq n$$$), representing a query of type $$$2$$$.

It is guaranteed that there's at least one query of type $$$2$$$.

## Output Format
For each query of type $$$2$$$, print one integer — the answer to the query.

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

## Note
For the first sample, there's initially only one possible permutation that satisfies the constraints: $$$[1, 2, 3]$$$, as it must have $$$0$$$ inversions.

After the query of type $$$1$$$, the array $$$b$$$ is $$$[0, 1, 0]$$$. The only permutation $$$p$$$ that produces this array is $$$[2, 1, 3]$$$. With this permutation, $$$b_2$$$ is equal to $$$1$$$ as $$$p_1 > p_2$$$.

Now solve the problem and return the code.