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
You are given a permutation $$$p_1, p_2, \dots, p_n$$$. Then, an undirected graph is constructed in the following way: add an edge between vertices $$$i$$$, $$$j$$$ such that $$$i < j$$$ if and only if $$$p_i > p_j$$$. Your task is to count the number of connected components in this graph.

Two vertices $$$u$$$ and $$$v$$$ belong to the same connected component if and only if there is at least one path along edges connecting $$$u$$$ and $$$v$$$.

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 a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the permutation.

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$) — the elements of the permutation.

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 one integer $$$k$$$ — the number of connected components.

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

## Note
Each separate test case is depicted in the image below. The colored squares represent the elements of the permutation. For one permutation, each color represents some connected component. The number of distinct colors is the answer.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 256.0 MB

# Problem
You have an array $$$a_1,a_2, \dots, a_n$$$. Each element initially has value $$$0$$$ and color $$$1$$$. You are also given $$$q$$$ queries to perform:

- Color $$$l$$$ $$$r$$$ $$$c$$$: Change the color of elements $$$a_l,a_{l+1},\cdots,a_r$$$ to $$$c$$$ ($$$1 \le l \le r \le n$$$, $$$1 \le c \le n$$$).
- Add $$$c$$$ $$$x$$$: Add $$$x$$$ to values of all elements $$$a_i$$$ ($$$1 \le i \le n$$$) of color $$$c$$$ ($$$1 \le c \le n$$$, $$$-10^9 \le x \le 10^9$$$).
- Query $$$i$$$: Print $$$a_i$$$ ($$$1 \le i \le n$$$).

## Input Format
The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 10^6$$$) — the length of array $$$a$$$ and the number of queries you have to perform.

Each of the next $$$q$$$ lines contains the query given in the form described in the problem statement.

## Output Format
Print the answers to the queries of the third type on separate lines.

## Examples
```input
5 8
Color 2 4 2
Add 2 2
Query 3
Color 4 5 3
Color 2 2 3
Add 3 3
Query 2
Query 5
```
```output
2
5
3
```
-----
```input
2 7
Add 1 7
Query 1
Add 2 4
Query 2
Color 1 1 1
Add 1 1
Query 2
```
```output
7
7
8
```

## Note
The first sample test is explained below. Blue, red and green represent colors $$$1$$$, $$$2$$$ and $$$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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Sam is a kindergartener, and there are $$$n$$$ children in his group. He decided to create a team with some of his children to play "brawl:go 2".

Sam has $$$n$$$ power-ups, the $$$i$$$-th has type $$$a_i$$$. A child's strength is equal to the number of different types among power-ups he has.

For a team of size $$$k$$$, Sam will distribute all $$$n$$$ power-ups to $$$k$$$ children in such a way that each of the $$$k$$$ children receives at least one power-up, and each power-up is given to someone.

For each integer $$$k$$$ from $$$1$$$ to $$$n$$$, find the minimum sum of strengths of a team of $$$k$$$ children Sam can get.

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

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — types of Sam's power-ups.

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

## Output Format
For every test case print $$$n$$$ integers.

The $$$k$$$-th integer should be equal to the minimum sum of strengths of children in the team of size $$$k$$$ that Sam can get.

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

## Note
One of the ways to give power-ups to minimise the sum of strengths in the first test case:

- $$$k = 1: \{1, 1, 2\}$$$
- $$$k = 2: \{1, 1\}, \{2\}$$$
- $$$k = 3: \{1\}, \{1\}, \{2\}$$$

One of the ways to give power-ups to minimise the sum of strengths in the second test case:

- $$$k = 1: \{1, 2, 2, 2, 4, 5\}$$$
- $$$k = 2: \{2, 2, 2, 4, 5\}, \{1\}$$$
- $$$k = 3: \{2, 2, 2, 5\}, \{1\}, \{4\}$$$
- $$$k = 4: \{2, 2, 2\}, \{1\}, \{4\}, \{5\}$$$
- $$$k = 5: \{2, 2\}, \{1\}, \{2\}, \{4\}, \{5\}$$$
- $$$k = 6: \{1\}, \{2\}, \{2\}, \{2\}, \{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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a positive integer $$$n$$$. Let's call some positive integer $$$a$$$ without leading zeroes palindromic if it remains the same after reversing the order of its digits. Find the number of distinct ways to express $$$n$$$ as a sum of positive palindromic integers. Two ways are considered different if the frequency of at least one palindromic integer is different in them. For example, $$$5=4+1$$$ and $$$5=3+1+1$$$ are considered different but $$$5=3+1+1$$$ and $$$5=1+3+1$$$ are considered the same.

Formally, you need to find the number of distinct multisets of positive palindromic integers the sum of which is equal to $$$n$$$.

Since the answer can be quite large, print it modulo $$$10^9+7$$$.

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

Each testcase contains a single line of input containing a single integer $$$n$$$ ($$$1\leq n\leq 4\cdot 10^4$$$) — the required sum of palindromic integers.

## Output Format
For each testcase, print a single integer denoting the required answer modulo $$$10^9+7$$$.

## Examples
```input
2
5
12
```
```output
7
74
```

## Note
For the first testcase, there are $$$7$$$ ways to partition $$$5$$$ as a sum of positive palindromic integers:

- $$$5=1+1+1+1+1$$$
- $$$5=1+1+1+2$$$
- $$$5=1+2+2$$$
- $$$5=1+1+3$$$
- $$$5=2+3$$$
- $$$5=1+4$$$
- $$$5=5$$$

For the second testcase, there are total $$$77$$$ ways to partition $$$12$$$ as a sum of positive integers but among them, the partitions $$$12=2+10$$$, $$$12=1+1+10$$$ and $$$12=12$$$ are not valid partitions of $$$12$$$ as a sum of positive palindromic integers because $$$10$$$ and $$$12$$$ are not palindromic. So, there are $$$74$$$ ways to partition $$$12$$$ as a sum of positive palindromic integers.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 512.0 MB

# Problem
Tokitsukaze has a sequence with length of $$$n$$$. She likes gems very much. There are $$$n$$$ kinds of gems. The gems of the $$$i$$$-th kind are on the $$$i$$$-th position, and there are $$$a_i$$$ gems of the same kind on that position. Define $$$G(l,r)$$$ as the multiset containing all gems on the segment $$$[l,r]$$$ (inclusive).

A multiset of gems can be represented as $$$S=[s_1,s_2,\ldots,s_n]$$$, which is a non-negative integer sequence of length $$$n$$$ and means that $$$S$$$ contains $$$s_i$$$ gems of the $$$i$$$-th kind in the multiset. A multiset $$$T=[t_1,t_2,\ldots,t_n]$$$ is a multisubset of $$$S=[s_1,s_2,\ldots,s_n]$$$ if and only if $$$t_i\le s_i$$$ for any $$$i$$$ satisfying $$$1\le i\le n$$$.

Now, given two positive integers $$$k$$$ and $$$p$$$, you need to calculate the result of

$$$$$$\sum_{l=1}^n \sum_{r=l}^n\sum\limits_{[t_1,t_2,\cdots,t_n] \subseteq G(l,r)}\left(\left(\sum_{i=1}^n p^{t_i}t_i^k\right)\left(\sum_{i=1}^n[t_i>0]\right)\right),$$$$$$

where $$$[t_i>0]=1$$$ if $$$t_i>0$$$ and $$$[t_i>0]=0$$$ if $$$t_i=0$$$.

Since the answer can be quite large, print it modulo $$$998\,244\,353$$$.

## Input Format
The first line contains three integers $$$n$$$, $$$k$$$ and $$$p$$$ ($$$1\le n \le 10^5$$$; $$$1\le k\le 10^5$$$; $$$2\le p\le 998\,244\,351$$$) — the length of the sequence, the numbers $$$k$$$ and $$$p$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 998\,244\,351$$$) — the number of gems on the $$$i$$$-th position.

## Output Format
Print a single integers — the result modulo $$$998\,244\,353$$$.

## Examples
```input
5 2 2
1 1 1 2 2
```
```output
6428
```
-----
```input
6 2 2
2 2 2 2 2 3
```
```output
338940
```

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$$$ of integers from $$$0$$$ to $$$n-1$$$ (each of them occurs exactly once). Initially, the permutation is not sorted (that is, $$$p_i>p_{i+1}$$$ for at least one $$$1 \le i \le n - 1$$$).

The permutation is called $$$X$$$-sortable for some non-negative integer $$$X$$$ if it is possible to sort the permutation by performing the operation below some finite number of times:

- Choose two indices $$$i$$$ and $$$j$$$ $$$(1 \le i \lt j \le n)$$$ such that $$$p_i \& p_j = X$$$.
- Swap $$$p_i$$$ and $$$p_j$$$.

Here $$$\&$$$ denotes the bitwise AND operation.

Find the maximum value of $$$X$$$ such that $$$p$$$ is $$$X$$$-sortable. It can be shown that there always exists some value of $$$X$$$ such that $$$p$$$ is $$$X$$$-sortable.

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

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

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, ..., p_n$$$ ($$$0 \le p_i \le n-1$$$, all $$$p_i$$$ are distinct)  — the elements of $$$p$$$. It is guaranteed that $$$p$$$ is not sorted.

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

## Output Format
For each test case output a single integer — the maximum value of $$$X$$$ such that $$$p$$$ is $$$X$$$-sortable.

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

## Note
In the first test case, the only $$$X$$$ for which the permutation is $$$X$$$-sortable are $$$X = 0$$$ and $$$X = 2$$$, maximum of which is $$$2$$$.

Sorting using $$$X = 0$$$:

- Swap $$$p_1$$$ and $$$p_4$$$, $$$p = [2, 1, 3, 0]$$$.
- Swap $$$p_3$$$ and $$$p_4$$$, $$$p = [2, 1, 0, 3]$$$.
- Swap $$$p_1$$$ and $$$p_3$$$, $$$p = [0, 1, 2, 3]$$$.

Sorting using $$$X = 2$$$:

- Swap $$$p_3$$$ and $$$p_4$$$, $$$p = [0, 1, 2, 3]$$$.

In the second test case, we must swap $$$p_1$$$ and $$$p_2$$$ which is possible only with $$$X = 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 $$$a$$$ of $$$n$$$ positive integers.

Let $$$\text{LIS}(a)$$$ denote the length of longest strictly increasing subsequence of $$$a$$$. For example,

- $$$\text{LIS}([2, \underline{1}, 1, \underline{3}])$$$ = $$$2$$$.
- $$$\text{LIS}([\underline{3}, \underline{5}, \underline{10}, \underline{20}])$$$ = $$$4$$$.
- $$$\text{LIS}([3, \underline{1}, \underline{2}, \underline{4}])$$$ = $$$3$$$.

We define array $$$a'$$$ as the array obtained after reversing the array $$$a$$$ i.e. $$$a' = [a_n, a_{n-1}, \ldots , a_1]$$$.

The beauty of array $$$a$$$ is defined as $$$min(\text{LIS}(a),\text{LIS}(a'))$$$.

Your task is to determine the maximum possible beauty of the array $$$a$$$ if you can rearrange the array $$$a$$$ arbitrarily.

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4)$$$  — the number of test cases. 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 array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2, \ldots ,a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$  — the 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, output a single integer  — the maximum possible beauty of $$$a$$$ after rearranging its elements arbitrarily.

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

## Note
In the first test case, $$$a$$$ = $$$[6, 6, 6]$$$ and $$$a'$$$ = $$$[6, 6, 6]$$$. $$$\text{LIS}(a) = \text{LIS}(a')$$$ = $$$1$$$. Hence the beauty is $$$min(1, 1) = 1$$$.

In the second test case, $$$a$$$ can be rearranged to $$$[2, 5, 4, 5, 4, 2]$$$. Then $$$a'$$$ = $$$[2, 4, 5, 4, 5, 2]$$$. $$$\text{LIS}(a) = \text{LIS}(a') = 3$$$. Hence the beauty is $$$3$$$ and it can be shown that this is the maximum possible beauty.

In the third test case, $$$a$$$ can be rearranged to $$$[1, 2, 3, 2]$$$. Then $$$a'$$$ = $$$[2, 3, 2, 1]$$$. $$$\text{LIS}(a) = 3$$$, $$$\text{LIS}(a') = 2$$$. Hence the beauty is $$$min(3, 2) = 2$$$ and it can be shown that $$$2$$$ is the maximum possible beauty.

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: 512.0 MB

# Problem
For a collection of integers $$$S$$$, define $$$\operatorname{mex}(S)$$$ as the smallest non-negative integer that does not appear in $$$S$$$.

NIT, the cleaver, decides to destroy the universe. He is not so powerful as Thanos, so he can only destroy the universe by snapping his fingers several times.

The universe can be represented as a 1-indexed array $$$a$$$ of length $$$n$$$. When NIT snaps his fingers, he does the following operation on the array:

- He selects positive integers $$$l$$$ and $$$r$$$ such that $$$1\le l\le r\le n$$$. Let $$$w=\operatorname{mex}(\{a_l,a_{l+1},\dots,a_r\})$$$. Then, for all $$$l\le i\le r$$$, set $$$a_i$$$ to $$$w$$$.

We say the universe is destroyed if and only if for all $$$1\le i\le n$$$, $$$a_i=0$$$ holds.

Find the minimum number of times NIT needs to snap his fingers to destroy the universe. That is, find the minimum number of operations NIT needs to perform to make all elements in the array equal to $$$0$$$.

## 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 one integer $$$n$$$ ($$$1\le n\le 10^5$$$).

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

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 one integer — the answer to the problem.

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

## Note
In the first test case, we do $$$0$$$ operations and all elements in the array are already equal to $$$0$$$.

In the second test case, one optimal way is doing the operation with $$$l=2$$$, $$$r=5$$$.

In the third test case, one optimal way is doing the operation twice, respectively with $$$l=4$$$, $$$r=4$$$ and $$$l=2$$$, $$$r=6$$$.

In the fourth test case, one optimal way is doing the operation with $$$l=1$$$, $$$r=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: 512.0 MB

# Problem
Fishingprince loves trees. A tree is a connected undirected graph without cycles.

Fishingprince has a tree of $$$n$$$ vertices. The vertices are numbered $$$1$$$ through $$$n$$$. Let $$$d(x,y)$$$ denote the shortest distance on the tree from vertex $$$x$$$ to vertex $$$y$$$, assuming that the length of each edge is $$$1$$$.

However, the tree was lost in an accident. Fortunately, Fishingprince still remembers some information about the tree. More specifically, for every triple of integers $$$x,y,z$$$ ($$$1\le x<y\le n$$$, $$$1\le z\le n$$$) he remembers whether $$$d(x,z)=d(y,z)$$$ or not.

Help him recover the structure of the tree, or report that no tree satisfying the constraints exists.

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

The first line of each test case contains an integer $$$n$$$ ($$$2\le n\le 100$$$) — the number of vertices in the tree.

Then $$$n-1$$$ lines follow. The $$$i$$$-th line of these $$$n-1$$$ lines contains $$$n-i$$$ strings of length $$$n$$$ consisting of 0 and 1. If the $$$k$$$-th character in the $$$j$$$-th string of the $$$i$$$-th line is 0, it means that $$$d(i,k)\ne d(i+j,k)$$$; if the $$$k$$$-th character in the $$$j$$$-th string of the $$$i$$$-th line is 1, it means that $$$d(i,k)=d(i+j,k)$$$.

It is guaranteed that in one input file,

- there are at most $$$2$$$ test cases that have $$$n>50$$$;
- there are at most $$$5$$$ test cases that have $$$n>20$$$.

## Output Format
For each test case:

- if no answer exists, output No;
- otherwise, on the first line output Yes. Then output $$$n-1$$$ lines. Each line should contain two integers $$$x,y$$$ ($$$1\le x,y\le n$$$), denoting an edge between vertices $$$x$$$ and $$$y$$$ of the tree. If there are multiple solutions, print any.

When printing Yes and No, you can print each letter in any case (upper or lower).

## Examples
```input
5
2
00
2
10
3
001 000
000
3
001 010
000
5
00000 01001 00000 01100
00000 10000 00000
00000 11010
00000
```
```output
Yes
1 2
No
Yes
1 3
2 3
No
Yes
1 2
1 4
2 3
2 5
```

Now solve the problem and return the code.