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

# Problem
Koishi is unconsciously permuting $$$n$$$ numbers: $$$1, 2, \ldots, n$$$.

She thinks the permutation $$$p$$$ is beautiful if $$$s=\sum\limits_{i=1}^{n-1} [p_i+1=p_{i+1}]$$$. $$$[x]$$$ equals to $$$1$$$ if $$$x$$$ holds, or $$$0$$$ otherwise.

For each $$$k\in[0,n-1]$$$, she wants to know the number of beautiful permutations of length $$$n$$$ satisfying $$$k=\sum\limits_{i=1}^{n-1}[p_i<p_{i+1}]$$$.

## Input Format
There is one line containing two intergers $$$n$$$ ($$$1 \leq n \leq 250\,000$$$) and $$$s$$$ ($$$0 \leq s < n$$$).

## Output Format
Print one line with $$$n$$$ intergers. The $$$i$$$-th integers represents the answer of $$$k=i-1$$$, modulo $$$998244353$$$.

## Examples
```input
2 0
```
```output
1 0
```
-----
```input
4 1
```
```output
0 3 6 0
```
-----
```input
8 3
```
```output
0 0 0 35 770 980 70 0
```

## Note
Let $$$f(p)=\sum\limits_{i=1}^{n-1}[p_i<p_{i+1}]$$$.

Testcase 1:

$$$[2,1]$$$ is the only beautiful permutation. And $$$f([2,1])=0$$$.

Testcase 2:

Beautiful permutations:

$$$[1,2,4,3]$$$, $$$[1,3,4,2]$$$, $$$[1,4,2,3]$$$, $$$[2,1,3,4]$$$, $$$[2,3,1,4]$$$, $$$[3,1,2,4]$$$, $$$[3,4,2,1]$$$, $$$[4,2,3,1]$$$, $$$[4,3,1,2]$$$. The first six of them satisfy $$$f(p)=2$$$, while others satisfy $$$f(p)=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
You are given a permutation $$$p_1,p_2,\ldots,p_n$$$ of length $$$n$$$ and a positive integer $$$k \le n$$$.

In one operation you can choose two indices $$$i$$$ and $$$j$$$ ($$$1 \le i < j \le n$$$) and swap $$$p_i$$$ with $$$p_j$$$.

Find the minimum number of operations needed to make the sum $$$p_1 + p_2 + \ldots + p_k$$$ as small as possible.

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

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 100$$$).

The second line of each test case contains $$$n$$$ integers $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i \le n$$$). It is guaranteed that the given numbers form a permutation of length $$$n$$$.

## Output Format
For each test case print one integer — the minimum number of operations needed to make the sum $$$p_1 + p_2 + \ldots + p_k$$$ as small as possible.

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

## Note
In the first test case, the value of $$$p_1 + p_2 + \ldots + p_k$$$ is initially equal to $$$2$$$, but the smallest possible value is $$$1$$$. You can achieve it by swapping $$$p_1$$$ with $$$p_3$$$, resulting in the permutation $$$[1, 3, 2]$$$.

In the second test case, the sum is already as small as possible, so the answer is $$$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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an array of $$$n$$$ positive integers $$$a_1,a_2,\ldots,a_n$$$.

In one operation you do the following:

1. Choose any integer $$$x$$$.
2. For all $$$i$$$ such that $$$a_i = x$$$, do $$$a_i := 0$$$ (assign $$$0$$$ to $$$a_i$$$).

Find the minimum number of operations required to sort the array in non-decreasing order.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). 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 second line of each test case contains $$$n$$$ positive integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$).

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

## Output Format
For each test case print one integer — the minimum number of operations required to sort the array in non-decreasing order.

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

## Note
In the first test case, you can choose $$$x = 3$$$ for the operation, the resulting array is $$$[0, 0, 2]$$$.

In the second test case, you can choose $$$x = 1$$$ for the first operation and $$$x = 3$$$ for the second operation, the resulting array is $$$[0, 0, 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: 1.5 seconds
Memory limit: 256.0 MB

# Problem
An array of $$$n$$$ positive integers $$$a_1,a_2,\ldots,a_n$$$ fell down on you from the skies, along with a positive integer $$$k \le n$$$.

You can apply the following operation at most $$$k$$$ times:

- Choose an index $$$1 \le i \le n$$$ and an integer $$$1 \le x \le 10^9$$$. Then do $$$a_i := x$$$ (assign $$$x$$$ to $$$a_i$$$).

Then build a complete undirected weighted graph with $$$n$$$ vertices numbered with integers from $$$1$$$ to $$$n$$$, where edge $$$(l, r)$$$ ($$$1 \le l < r \le n$$$) has weight $$$\min(a_{l},a_{l+1},\ldots,a_{r})$$$.

You have to find the maximum possible diameter of the resulting graph after performing at most $$$k$$$ operations.

The diameter of a graph is equal to $$$\max\limits_{1 \le u < v \le n}{\operatorname{d}(u, v)}$$$, where $$$\operatorname{d}(u, v)$$$ is the length of the shortest path between vertex $$$u$$$ and vertex $$$v$$$.

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

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le n$$$).

The second line of each test case contains $$$n$$$ positive integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

## Output Format
For each test case print one integer — the maximum possible diameter of the graph after performing at most $$$k$$$ operations.

## Examples
```input
6
3 1
2 4 1
3 2
1 9 84
3 1
10 2 6
3 2
179 17 1000000000
2 1
5 9
2 2
4 2
```
```output
4
168
10
1000000000
9
1000000000
```

## Note
In the first test case, one of the optimal arrays is $$$[2,4,5]$$$.

The graph built on this array:

$$$\operatorname{d}(1, 2) = \operatorname{d}(1, 3) = 2$$$ and $$$\operatorname{d}(2, 3) = 4$$$, so the diameter is equal to $$$\max(2,2,4) = 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: 3.5 seconds
Memory limit: 512.0 MB

# Problem
This version of the problem differs from the next one only in the constraint on $$$t$$$. You can make hacks only if both versions of the problem are solved.

You are given two positive integers $$$l$$$ and $$$r$$$.

Count the number of distinct triplets of integers $$$(i, j, k)$$$ such that $$$l \le i < j < k \le r$$$ and $$$\operatorname{lcm}(i,j,k) \ge i + j + k$$$.

Here $$$\operatorname{lcm}(i, j, k)$$$ denotes the least common multiple (LCM) of integers $$$i$$$, $$$j$$$, and $$$k$$$.

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

The only line for each test case contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 2 \cdot 10^5$$$, $$$l + 2 \le r$$$).

## Output Format
For each test case print one integer — the number of suitable triplets.

## Examples
```input
5
1 4
3 5
8 86
68 86
6 86868
```
```output
3
1
78975
969
109229059713337
```

## Note
In the first test case, there are $$$3$$$ suitable triplets:

- $$$(1,2,3)$$$,
- $$$(1,3,4)$$$,
- $$$(2,3,4)$$$.

In the second test case, there is $$$1$$$ suitable triplet:

- $$$(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 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: 3.5 seconds
Memory limit: 512.0 MB

# Problem
This version of the problem differs from the previous one only in the constraint on $$$t$$$. You can make hacks only if both versions of the problem are solved.

You are given two positive integers $$$l$$$ and $$$r$$$.

Count the number of distinct triplets of integers $$$(i, j, k)$$$ such that $$$l \le i < j < k \le r$$$ and $$$\operatorname{lcm}(i,j,k) \ge i + j + k$$$.

Here $$$\operatorname{lcm}(i, j, k)$$$ denotes the least common multiple (LCM) of integers $$$i$$$, $$$j$$$, and $$$k$$$.

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

The only line for each test case contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 2 \cdot 10^5$$$, $$$l + 2 \le r$$$).

## Output Format
For each test case print one integer — the number of suitable triplets.

## Examples
```input
5
1 4
3 5
8 86
68 86
6 86868
```
```output
3
1
78975
969
109229059713337
```

## Note
In the first test case, there are $$$3$$$ suitable triplets:

- $$$(1,2,3)$$$,
- $$$(1,3,4)$$$,
- $$$(2,3,4)$$$.

In the second test case, there is $$$1$$$ suitable triplet:

- $$$(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 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.5 seconds
Memory limit: 768.0 MB

# Problem
A tree is a connected undirected graph without cycles. A weighted tree has a weight assigned to each edge. The degree of a vertex is the number of edges connected to this vertex.

You are given a weighted tree with $$$n$$$ vertices, each edge has a weight of $$$1$$$. Let $$$L$$$ be the set of vertices with degree equal to $$$1$$$.

You have to answer $$$q$$$ independent queries. In the $$$i$$$-th query:

1. You are given a positive integer $$$x_i$$$.
2. For all $$$u,v \in L$$$ such that $$$u < v$$$, add edge $$$(u, v)$$$ with weight $$$x_i$$$ to the graph (initially the given tree).
3. Find the diameter of the resulting graph.

The diameter of a graph is equal to $$$\max\limits_{1 \le u < v \le n}{\operatorname{d}(u, v)}$$$, where $$$\operatorname{d}(u, v)$$$ is the length of the shortest path between vertex $$$u$$$ and vertex $$$v$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$3 \le n \le 10^6$$$).

The second line contains $$$n - 1$$$ integers $$$p_2,p_3,\ldots,p_n$$$ ($$$1 \le p_i < i$$$) indicating that there is an edge between vertices $$$i$$$ and $$$p_i$$$. It is guaranteed that the given edges form a tree.

The third line contains a single integer $$$q$$$ ($$$1 \le q \le 10$$$).

The fourth line contains $$$q$$$ integers $$$x_1,x_2,\ldots,x_q$$$ ($$$1 \le x_i \le n$$$). All $$$x_i$$$ are distinct.

## Output Format
Print $$$q$$$ integers in a single line — the answers to the queries.

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

## Note
The graph in the first test after adding the edges:

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
A sequence of $$$n$$$ numbers is called permutation if it contains all numbers from $$$1$$$ to $$$n$$$ exactly once. For example, the sequences $$$[3, 1, 4, 2]$$$, [$$$1$$$] and $$$[2,1]$$$ are permutations, but $$$[1,2,1]$$$, $$$[0,1]$$$ and $$$[1,3,4]$$$ are not.

For a given number $$$n$$$ you need to make a permutation $$$p$$$ such that two requirements are satisfied at the same time:

- For each element $$$p_i$$$, at least one of its neighbors has a value that differs from the value of $$$p_i$$$ by one. That is, for each element $$$p_i$$$ ($$$1 \le i \le n$$$), at least one of its neighboring elements (standing to the left or right of $$$p_i$$$) must be $$$p_i + 1$$$, or $$$p_i - 1$$$.
- the permutation must have no fixed points. That is, for every $$$i$$$ ($$$1 \le i \le n$$$), $$$p_i \neq i$$$ must be satisfied.

Let's call the permutation that satisfies these requirements funny.

For example, let $$$n = 4$$$. Then [$$$4, 3, 1, 2$$$] is a funny permutation, since:

- to the right of $$$p_1=4$$$ is $$$p_2=p_1-1=4-1=3$$$;
- to the left of $$$p_2=3$$$ is $$$p_1=p_2+1=3+1=4$$$;
- to the right of $$$p_3=1$$$ is $$$p_4=p_3+1=1+1=2$$$;
- to the left of $$$p_4=2$$$ is $$$p_3=p_4-1=2-1=1$$$.
- for all $$$i$$$ is $$$p_i \ne i$$$.

For a given positive integer $$$n$$$, output any funny permutation of length $$$n$$$, or output -1 if funny permutation of length $$$n$$$ does not exist.

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

The description of the test cases follows.

Each test case consists of f single line containing one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

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 on a separate line:

- any funny permutation $$$p$$$ of length $$$n$$$;
- or the number -1 if the permutation you are looking for does not exist.

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

## Note
The first test case is explained in the problem statement.

In the second test case, it is not possible to make the required permutation: permutations $$$[1, 2, 3]$$$, $$$[1, 3, 2]$$$, $$$[2, 1, 3]$$$, $$$[3, 2, 1]$$$ have fixed points, and in $$$[2, 3, 1]$$$ and $$$[3, 1, 2]$$$ the first condition is met not for all positions.

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
The girl named Masha was walking in the forest and found a complete binary tree of height $$$n$$$ and a permutation $$$p$$$ of length $$$m=2^n$$$.

A complete binary tree of height $$$n$$$ is a rooted tree such that every vertex except the leaves has exactly two sons, and the length of the path from the root to any of the leaves is $$$n$$$. The picture below shows the complete binary tree for $$$n=2$$$.

A permutation is an array consisting of $$$n$$$ different integers from $$$1$$$ to $$$n$$$. For example, [$$$2,3,1,5,4$$$] is a permutation, but [$$$1,2,2$$$] is not ($$$2$$$ occurs twice), and [$$$1,3,4$$$] is also not a permutation ($$$n=3$$$, but there is $$$4$$$ in the array).

Let's enumerate $$$m$$$ leaves of this tree from left to right. The leaf with the number $$$i$$$ contains the value $$$p_i$$$ ($$$1 \le i \le m$$$).

For example, if $$$n = 2$$$, $$$p = [3, 1, 4, 2]$$$, the tree will look like this:

Masha considers a tree beautiful if the values in its leaves are ordered from left to right in increasing order.

In one operation, Masha can choose any non-leaf vertex of the tree and swap its left and right sons (along with their subtrees).

For example, if Masha applies this operation to the root of the tree discussed above, it will take the following form:

Help Masha understand if she can make a tree beautiful in a certain number of operations. If she can, then output the minimum number of operations to make the tree beautiful.

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

In each test case, the first line contains an integer $$$m$$$ ($$$1 \le m \le 262144$$$), which is a power of two  — the size of the permutation $$$p$$$.

The second line contains $$$m$$$ integers: $$$p_1, p_2, \dots, p_m$$$ ($$$1 \le p_i \le m$$$) — the permutation $$$p$$$.

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

## Output Format
For each test case in a separate line, print the minimum possible number of operations for which Masha will be able to make the tree beautiful or -1, if this is not possible.

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

## Note
Consider the first test.

In the first test case, you can act like this (the vertex to which the operation is applied at the current step is highlighted in purple):

In the second test case, it can be shown that it is impossible to make a tree beautiful.

In the third test case, the tree is already beautiful.

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 talked to Polycarp and asked him a question. You know that when he wants to answer "yes", he repeats Yes many times in a row.

Because of the noise, you only heard part of the answer — some substring of it. That is, if he answered YesYes, then you could hear esY, YesYes, sYes, e, but you couldn't Yess, YES or se.

Determine if it is true that the given string $$$s$$$ is a substring of YesYesYes... (Yes repeated many times in a row).

## Input Format
The first line of input data contains the singular $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases in the test.

Each test case is described by a single string of Latin letters $$$s$$$ ($$$1 \le |s| \le 50$$$) — the part of Polycarp's answer that you heard, where $$$|s|$$$ — is the length of the string $$$s$$$.

## Output Format
Output $$$t$$$ lines, each of which is the answer to the corresponding test case. As an answer, output "YES" if the specified string $$$s$$$ is a substring of the string YesYesYes...Yes (the number of words Yes is arbitrary), and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

## Examples
```input
12
YES
esYes
codeforces
es
se
YesY
esYesYesYesYesYesYe
seY
Yess
sY
o
Yes
```
```output
NO
YES
NO
YES
NO
YES
YES
NO
NO
YES
NO
YES
```

Now solve the problem and return the code.