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
The only difference between problems C1 and C2 is that all values in input of problem C1 are distinct (this condition may be false for problem C2).

You are given a sequence $$$a$$$ consisting of $$$n$$$ integers.

You are making a sequence of moves. During each move you must take either the leftmost element of the sequence or the rightmost element of the sequence, write it down and remove it from the sequence. Your task is to write down a strictly increasing sequence, and among all such sequences you should take the longest (the length of the sequence is the number of elements in it).

For example, for the sequence $$$[1, 2, 4, 3, 2]$$$ the answer is $$$4$$$ (you take $$$1$$$ and the sequence becomes $$$[2, 4, 3, 2]$$$, then you take the rightmost element $$$2$$$ and the sequence becomes $$$[2, 4, 3]$$$, then you take $$$3$$$ and the sequence becomes $$$[2, 4]$$$ and then you take $$$4$$$ and the sequence becomes $$$[2]$$$, the obtained increasing sequence is $$$[1, 2, 3, 4]$$$).

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of elements in $$$a$$$.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

## Output Format
In the first line of the output print $$$k$$$ — the maximum number of elements in a strictly increasing sequence you can obtain.

In the second line print a string $$$s$$$ of length $$$k$$$, where the $$$j$$$-th character of this string $$$s_j$$$ should be 'L' if you take the leftmost element during the $$$j$$$-th move and 'R' otherwise. If there are multiple answers, you can print any.

## Examples
```input
5
1 2 4 3 2
```
```output
4
LRRR
```
-----
```input
7
1 3 5 6 5 4 2
```
```output
6
LRLRRR
```
-----
```input
3
2 2 2
```
```output
1
R
```
-----
```input
4
1 2 4 3
```
```output
4
LLRR
```

## Note
The first example is described in the problem statement.

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 two arrays $$$a$$$ and $$$b$$$, both of length $$$n$$$. All elements of both arrays are from $$$0$$$ to $$$n-1$$$.

You can reorder elements of the array $$$b$$$ (if you want, you may leave the order of elements as it is). After that, let array $$$c$$$ be the array of length $$$n$$$, the $$$i$$$-th element of this array is $$$c_i = (a_i + b_i) \% n$$$, where $$$x \% y$$$ is $$$x$$$ modulo $$$y$$$.

Your task is to reorder elements of the array $$$b$$$ to obtain the lexicographically minimum possible array $$$c$$$.

Array $$$x$$$ of length $$$n$$$ is lexicographically less than array $$$y$$$ of length $$$n$$$, if there exists such $$$i$$$ ($$$1 \le i \le n$$$), that $$$x_i < y_i$$$, and for any $$$j$$$ ($$$1 \le j < i$$$) $$$x_j = y_j$$$.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of elements in $$$a$$$, $$$b$$$ and $$$c$$$.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < n$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

The third line of the input contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_i < n$$$), where $$$b_i$$$ is the $$$i$$$-th element of $$$b$$$.

## Output Format
Print the lexicographically minimum possible array $$$c$$$. Recall that your task is to reorder elements of the array $$$b$$$ and obtain the lexicographically minimum possible array $$$c$$$, where the $$$i$$$-th element of $$$c$$$ is $$$c_i = (a_i + b_i) \% n$$$.

## Examples
```input
4
0 1 2 1
3 2 1 1
```
```output
1 0 0 2
```
-----
```input
7
2 5 1 5 3 4 3
2 4 3 5 6 5 1
```
```output
0 0 0 1 0 2 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
There are $$$n$$$ people in a row. The height of the $$$i$$$-th person is $$$a_i$$$. You can choose any subset of these people and try to arrange them into a balanced circle.

A balanced circle is such an order of people that the difference between heights of any adjacent people is no more than $$$1$$$. For example, let heights of chosen people be $$$[a_{i_1}, a_{i_2}, \dots, a_{i_k}]$$$, where $$$k$$$ is the number of people you choose. Then the condition $$$|a_{i_j} - a_{i_{j + 1}}| \le 1$$$ should be satisfied for all $$$j$$$ from $$$1$$$ to $$$k-1$$$ and the condition $$$|a_{i_1} - a_{i_k}| \le 1$$$ should be also satisfied. $$$|x|$$$ means the absolute value of $$$x$$$. It is obvious that the circle consisting of one person is balanced.

Your task is to choose the maximum number of people and construct a balanced circle consisting of all chosen people. It is obvious that the circle consisting of one person is balanced so the answer always exists.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of people.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$), where $$$a_i$$$ is the height of the $$$i$$$-th person.

## Output Format
In the first line of the output print $$$k$$$ — the number of people in the maximum balanced circle.

In the second line print $$$k$$$ integers $$$res_1, res_2, \dots, res_k$$$, where $$$res_j$$$ is the height of the $$$j$$$-th person in the maximum balanced circle. The condition $$$|res_{j} - res_{j + 1}| \le 1$$$ should be satisfied for all $$$j$$$ from $$$1$$$ to $$$k-1$$$ and the condition $$$|res_{1} - res_{k}| \le 1$$$ should be also satisfied.

## Examples
```input
7
4 3 5 1 2 2 1
```
```output
5
2 1 1 2 3
```
-----
```input
5
3 7 5 1 5
```
```output
2
5 5
```
-----
```input
3
5 1 4
```
```output
2
4 5
```
-----
```input
7
2 2 3 2 1 2 2
```
```output
7
1 2 2 2 2 3 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 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
Vasya has a pile, that consists of some number of stones. $$$n$$$ times he either took one stone from the pile or added one stone to the pile. The pile was non-empty before each operation of taking one stone from the pile.

You are given $$$n$$$ operations which Vasya has made. Find the minimal possible number of stones that can be in the pile after making these operations.

## Input Format
The first line contains one positive integer $$$n$$$ — the number of operations, that have been made by Vasya ($$$1 \leq n \leq 100$$$).

The next line contains the string $$$s$$$, consisting of $$$n$$$ symbols, equal to "-" (without quotes) or "+" (without quotes). If Vasya took the stone on $$$i$$$-th operation, $$$s_i$$$ is equal to "-" (without quotes), if added, $$$s_i$$$ is equal to "+" (without quotes).

## Output Format
Print one integer — the minimal possible number of stones that can be in the pile after these $$$n$$$ operations.

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

## Note
In the first test, if Vasya had $$$3$$$ stones in the pile at the beginning, after making operations the number of stones will be equal to $$$0$$$. It is impossible to have less number of piles, so the answer is $$$0$$$. Please notice, that the number of stones at the beginning can't be less, than $$$3$$$, because in this case, Vasya won't be able to take a stone on some operation (the pile will be empty).

In the second test, if Vasya had $$$0$$$ stones in the pile at the beginning, after making operations the number of stones will be equal to $$$4$$$. It is impossible to have less number of piles because after making $$$4$$$ operations the number of stones in the pile increases on $$$4$$$ stones. So, the answer is $$$4$$$.

In the third test, if Vasya had $$$1$$$ stone in the pile at the beginning, after making operations the number of stones will be equal to $$$1$$$. It can be proved, that it is impossible to have less number of stones after making the operations.

In the fourth test, if Vasya had $$$0$$$ stones in the pile at the beginning, after making operations the number of stones will be equal to $$$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 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
Let's call an array of non-negative integers $$$a_1, a_2, \ldots, a_n$$$ a $$$k$$$-extension for some non-negative integer $$$k$$$ if for all possible pairs of indices $$$1 \leq i, j \leq n$$$ the inequality $$$k \cdot |i - j| \leq min(a_i, a_j)$$$ is satisfied. The expansion coefficient of the array $$$a$$$ is the maximal integer $$$k$$$ such that the array $$$a$$$ is a $$$k$$$-extension. Any array is a 0-expansion, so the expansion coefficient always exists.

You are given an array of non-negative integers $$$a_1, a_2, \ldots, a_n$$$. Find its expansion coefficient.

## Input Format
The first line contains one positive integer $$$n$$$ — the number of elements in the array $$$a$$$ ($$$2 \leq n \leq 300\,000$$$). The next line contains $$$n$$$ non-negative integers $$$a_1, a_2, \ldots, a_n$$$, separated by spaces ($$$0 \leq a_i \leq 10^9$$$).

## Output Format
Print one non-negative integer — expansion coefficient of the array $$$a_1, a_2, \ldots, a_n$$$.

## Examples
```input
4
6 4 5 5
```
```output
1
```
-----
```input
3
0 1 2
```
```output
0
```
-----
```input
4
821 500 479 717
```
```output
239
```

## Note
In the first test, the expansion coefficient of the array $$$[6, 4, 5, 5]$$$ is equal to $$$1$$$ because $$$|i-j| \leq min(a_i, a_j)$$$, because all elements of the array satisfy $$$a_i \geq 3$$$. On the other hand, this array isn't a $$$2$$$-extension, because $$$6 = 2 \cdot |1 - 4| \leq min(a_1, a_4) = 5$$$ is false.

In the second test, the expansion coefficient of the array $$$[0, 1, 2]$$$ is equal to $$$0$$$ because this array is not a $$$1$$$-extension, but it is $$$0$$$-extension.

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
Tom loves vowels, and he likes long words with many vowels. His favorite words are vowelly words. We say a word of length $$$k$$$ is vowelly if there are positive integers $$$n$$$ and $$$m$$$ such that $$$n\cdot m = k$$$ and when the word is written by using $$$n$$$ rows and $$$m$$$ columns (the first row is filled first, then the second and so on, with each row filled from left to right), every vowel of the English alphabet appears at least once in every row and every column.

You are given an integer $$$k$$$ and you must either print a vowelly word of length $$$k$$$ or print $$$-1$$$ if no such word exists.

In this problem the vowels of the English alphabet are 'a', 'e', 'i', 'o' ,'u'.

## Input Format
Input consists of a single line containing the integer $$$k$$$ ($$$1\leq k \leq 10^4$$$) — the required length.

## Output Format
The output must consist of a single line, consisting of a vowelly word of length $$$k$$$ consisting of lowercase English letters if it exists or $$$-1$$$ if it does not.

If there are multiple possible words, you may output any of them.

## Examples
```input
7
```
```output
-1
```
-----
```input
36
```
```output
agoeuioaeiruuimaeoieauoweouoiaouimae
```

## Note
In the second example, the word "agoeuioaeiruuimaeoieauoweouoiaouimae" can be arranged into the following $$$6 \times 6$$$ grid:

It is easy to verify that every row and every column contain all the vowels.

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
Given a positive integer $$$m$$$, we say that a sequence $$$x_1, x_2, \dots, x_n$$$ of positive integers is $$$m$$$-cute if for every index $$$i$$$ such that $$$2 \le i \le n$$$ it holds that $$$x_i = x_{i - 1} + x_{i - 2} + \dots + x_1 + r_i$$$ for some positive integer $$$r_i$$$ satisfying $$$1 \le r_i \le m$$$.

You will be given $$$q$$$ queries consisting of three positive integers $$$a$$$, $$$b$$$ and $$$m$$$. For each query you must determine whether or not there exists an $$$m$$$-cute sequence whose first term is $$$a$$$ and whose last term is $$$b$$$. If such a sequence exists, you must additionally find an example of it.

## Input Format
The first line contains an integer number $$$q$$$ ($$$1 \le q \le 10^3$$$) — the number of queries.

Each of the following $$$q$$$ lines contains three integers $$$a$$$, $$$b$$$, and $$$m$$$ ($$$1 \le a, b, m \le 10^{14}$$$, $$$a \leq b$$$), describing a single query.

## Output Format
For each query, if no $$$m$$$-cute sequence whose first term is $$$a$$$ and whose last term is $$$b$$$ exists, print $$$-1$$$.

Otherwise print an integer $$$k$$$ ($$$1 \le k \leq 50$$$), followed by $$$k$$$ integers $$$x_1, x_2, \dots, x_k$$$ ($$$1 \le x_i \le 10^{14}$$$). These integers must satisfy $$$x_1 = a$$$, $$$x_k = b$$$, and that the sequence $$$x_1, x_2, \dots, x_k$$$ is $$$m$$$-cute.

It can be shown that under the problem constraints, for each query either no $$$m$$$-cute sequence exists, or there exists one with at most $$$50$$$ terms.

If there are multiple possible sequences, you may print any of them.

## Examples
```input
2
5 26 2
3 9 1
```
```output
4 5 6 13 26
-1
```

## Note
Consider the sample. In the first query, the sequence $$$5, 6, 13, 26$$$ is valid since $$$6 = 5 + \bf{\color{blue} 1}$$$, $$$13 = 6 + 5 + {\bf\color{blue} 2}$$$ and $$$26 = 13 + 6 + 5 + {\bf\color{blue} 2}$$$ have the bold values all between $$$1$$$ and $$$2$$$, so the sequence is $$$2$$$-cute. Other valid sequences, such as $$$5, 7, 13, 26$$$ are also accepted.

In the second query, the only possible $$$1$$$-cute sequence starting at $$$3$$$ is $$$3, 4, 8, 16, \dots$$$, which does not contain $$$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 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
We have three positive integers $$$a$$$, $$$b$$$ and $$$c$$$. You don't know their values, but you know some information about them. Consider all three pairwise sums, i.e. the numbers $$$a+b$$$, $$$a+c$$$ and $$$b+c$$$. You know exactly two (any) of three pairwise sums.

Your task is to find such three positive integers $$$a$$$, $$$b$$$ and $$$c$$$ which match the given information. It means that if you consider $$$a+b$$$, $$$a+c$$$ and $$$b+c$$$, two out of all three of them are given in the input. Among all such triples, you must choose one with the minimum possible sum $$$a+b+c$$$, and among all triples with the minimum sum, you can print any.

You have to process $$$q$$$ independent queries.

## Input Format
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 1000$$$) — the number of queries.

The next $$$q$$$ lines contain queries. Each query is given as two integers $$$x$$$ and $$$y$$$ ($$$2 \le x, y \le 2 \cdot 10^9$$$), where $$$x$$$ and $$$y$$$ are any two out of the three numbers $$$a+b$$$, $$$a+c$$$ and $$$b+c$$$.

## Output Format
For each query print the answer to it: three positive integers $$$a$$$, $$$b$$$ and $$$c$$$ consistent with the given information. Among all such triples, you have to choose one with the minimum possible sum $$$a+b+c$$$. Among all triples with the minimum sum, you can print any.

## Examples
```input
3
123 13
2 2
2000000000 2000000000
```
```output
111 1 12
1 1 1
1999999999 1 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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Every day Kotlin heroes analyze the statistics of their website. For $$$n$$$ days, they wrote out $$$n$$$ numbers $$$a_1, a_2, \dots, a_n$$$, where $$$a_i$$$ is the number of visits on the $$$i$$$-th day.

They believe that a day is bad if there are at least $$$2$$$ days before it with a strictly greater number of visits. For example, if $$$n=8$$$ and $$$a=[3, 1, 4, 1, 5, 9, 2, 6]$$$, then the day $$$4$$$ is bad (because $$$a_4=1$$$, but there are $$$a_1=3$$$ and $$$a_3=4$$$). Also, the day with the number $$$7$$$ is bad too.

Write a program that finds the number of bad days.

## Input Format
The first line contains an integer $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$), where $$$n$$$ is the number of days. The second line contains $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the number of website visits on the $$$i$$$-th day.

## Output Format
Print the number of bad days, i.e. such days that there are at least two days before it with a strictly greater number of visits.

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

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

# Problem
Everyone knows that two consecutive (adjacent) "minus" signs can be replaced with a single "plus" sign.

You are given the string $$$s$$$, consisting of "plus" and "minus" signs only. Zero or more operations can be performed with it. In each operation you can choose any two adjacent "minus" signs, and replace them with a single "plus" sign. Thus, in one operation, the length of the string is reduced by exactly $$$1$$$.

You are given two strings $$$s$$$ and $$$t$$$. Determine if you can use $$$0$$$ or more operations to get the string $$$t$$$ from the string $$$s$$$.

## Input Format
The first line of the input contains an integer $$$k$$$ ($$$1 \le k \le 10^5$$$), denoting the number of test cases in the input. The following lines contain descriptions of the test sets, each set consists of two lines. First comes the line containing $$$s$$$ (the length of the line $$$s$$$ does not exceed $$$2\cdot10^5$$$), then comes the line containing $$$t$$$ (the length of the line $$$t$$$ does not exceed $$$2\cdot10^5$$$). The lines $$$s$$$ and $$$t$$$ are non-empty, and they contain only "plus" and "minus" signs.

The sum of the lengths of lines $$$s$$$ over all test cases in the input does not exceed $$$2\cdot10^5$$$. Similarly, the sum of the lengths of lines $$$t$$$ over all test cases in the input does not exceed $$$2\cdot10^5$$$.

## Output Format
Print $$$k$$$ lines: the $$$i$$$-th line must contain YES if the answer to the $$$i$$$-th test case is positive, otherwise NO. Print YES and NO using uppercase letters only.

## Examples
```input
5
-+--+
-+++
--------
-+--+-
-
+
--
---
+++
+++
```
```output
YES
YES
NO
NO
YES
```

Now solve the problem and return the code.