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

# Problem
This is an easier version of the next problem. In this version, $$$q = 0$$$.

A sequence of integers is called nice if its elements are arranged in blocks like in $$$[3, 3, 3, 4, 1, 1]$$$. Formally, if two elements are equal, everything in between must also be equal.

Let's define difficulty of a sequence as a minimum possible number of elements to change to get a nice sequence. However, if you change at least one element of value $$$x$$$ to value $$$y$$$, you must also change all other elements of value $$$x$$$ into $$$y$$$ as well. For example, for $$$[3, 3, 1, 3, 2, 1, 2]$$$ it isn't allowed to change first $$$1$$$ to $$$3$$$ and second $$$1$$$ to $$$2$$$. You need to leave $$$1$$$'s untouched or change them to the same value.

You are given a sequence of integers $$$a_1, a_2, \ldots, a_n$$$ and $$$q$$$ updates.

Each update is of form "$$$i$$$ $$$x$$$" — change $$$a_i$$$ to $$$x$$$. Updates are not independent (the change stays for the future).

Print the difficulty of the initial sequence and of the sequence after every update.

## Input Format
The first line contains integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 200\,000$$$, $$$q = 0$$$), the length of the sequence and the number of the updates.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 200\,000$$$), the initial sequence.

Each of the following $$$q$$$ lines contains integers $$$i_t$$$ and $$$x_t$$$ ($$$1 \le i_t \le n$$$, $$$1 \le x_t \le 200\,000$$$), the position and the new value for this position.

## Output Format
Print $$$q+1$$$ integers, the answer for the initial sequence and the answer after every update.

## Examples
```input
5 0
3 7 3 7 3
```
```output
2
```
-----
```input
10 0
1 2 1 2 3 1 1 1 50 1
```
```output
4
```
-----
```input
6 0
6 6 3 3 4 4
```
```output
0
```
-----
```input
7 0
3 3 1 3 2 1 2
```
```output
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: 5.0 seconds
Memory limit: 256.0 MB

# Problem
This is a harder version of the problem. In this version $$$q \le 200\,000$$$.

A sequence of integers is called nice if its elements are arranged in blocks like in $$$[3, 3, 3, 4, 1, 1]$$$. Formally, if two elements are equal, everything in between must also be equal.

Let's define difficulty of a sequence as a minimum possible number of elements to change to get a nice sequence. However, if you change at least one element of value $$$x$$$ to value $$$y$$$, you must also change all other elements of value $$$x$$$ into $$$y$$$ as well. For example, for $$$[3, 3, 1, 3, 2, 1, 2]$$$ it isn't allowed to change first $$$1$$$ to $$$3$$$ and second $$$1$$$ to $$$2$$$. You need to leave $$$1$$$'s untouched or change them to the same value.

You are given a sequence of integers $$$a_1, a_2, \ldots, a_n$$$ and $$$q$$$ updates.

Each update is of form "$$$i$$$ $$$x$$$" — change $$$a_i$$$ to $$$x$$$. Updates are not independent (the change stays for the future).

Print the difficulty of the initial sequence and of the sequence after every update.

## Input Format
The first line contains integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 200\,000$$$, $$$0 \le q \le 200\,000$$$), the length of the sequence and the number of the updates.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 200\,000$$$), the initial sequence.

Each of the following $$$q$$$ lines contains integers $$$i_t$$$ and $$$x_t$$$ ($$$1 \le i_t \le n$$$, $$$1 \le x_t \le 200\,000$$$), the position and the new value for this position.

## Output Format
Print $$$q+1$$$ integers, the answer for the initial sequence and the answer after every update.

## Examples
```input
5 6
1 2 1 2 1
2 1
4 1
5 3
2 3
4 2
2 1
```
```output
2
1
0
0
2
3
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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarp is choosing three problems for creating a programming test. Totally he has $$$n$$$ problems in his list. The complexity of the $$$i$$$-th problem equals $$$r_i$$$. All problems are numerated from $$$1$$$ to $$$n$$$.

Help Polycarp to choose such three problems $$$a$$$, $$$b$$$ and $$$c$$$, so that the complexity of the first problem strictly less than the complexity of second problem and the complexity of the second problem is strictly less than the complexity of the third problem. So, for chosen problems $$$a$$$, $$$b$$$ and $$$c$$$ it should be true that $$$r_a < r_b < r_c$$$.

If Polycarp can choose three problems in different ways, you can print any of them.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$3 \le n \le 3000$$$) — the number of problems in Polycarp's list.

The second line of the input contains $$$n$$$ integers $$$r_1, r_2, \dots, r_n$$$ ($$$1 \le r_i \le 10^9$$$), where $$$r_i$$$ is the complexity of the $$$i$$$-th problem.

## Output Format
If Polycarp has no ways to choose three problems, you should print three numbers -1. Ih there is a way to choose them, you should print three different integers $$$a, b, c$$$ ($$$1 \le a, b, c \le n$$$), where $$$a$$$ is the number of the first chosen problem, $$$b$$$ is the number of the second chosen problem and $$$c$$$ is the number of the third chosen problem.

## Examples
```input
6
3 1 4 1 5 9
```
```output
4 1 3
```
-----
```input
5
1 1000000000 1 1000000000 1
```
```output
-1 -1 -1
```
-----
```input
9
10 10 11 10 10 10 10 10 1
```
```output
9 8 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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
The Golden Ring is the special tourist route in Berland. This route consists of $$$n$$$ cities and the cyclic railway route. Cities are numbered from $$$1$$$ to $$$n$$$ so that:

- the next city for $$$1$$$ is the city $$$2$$$,
- the next city for $$$2$$$ is the city $$$3$$$,
- ...
- the next city for $$$n$$$ is the city $$$1$$$.

Thus, the route is a cycle, cities are numbered in the direction of travel (the route is directed in one way).

Blogger Polycarp wants to start his journey in the city $$$1$$$. For each city he knows the value $$$a_i$$$ — how many selfies he wants to do in $$$i$$$-th city. He can take no more than one selfie in one visit to each city. Since he is traveling by train, he can't skip the city (he always moves from the city $$$i$$$ to the city $$$i+1$$$ for $$$1 \le i < n$$$ and from $$$n$$$ to $$$1$$$). Thus, when the train stops in the city, Polycarp must visit this city. If Polycarp visits the city multiple times, all visits are counted separately.

What is the least number of city visits Polycarp will have to complete to fulfill his plan for the number of selfies for each city? Note that he always visits the city $$$1$$$, since it is this city that his journey begins in.

## Input Format
The first line contains an integer $$$n$$$ ($$$3 \le n \le 2\cdot10^5$$$) — the number of cities in the Golden Ring of Berland.

The next line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$), where $$$a_i$$$ is equal to the required number of selfies in the $$$i$$$-th city.

It is guaranteed that at least one of the numbers $$$a_i$$$ is strictly greater than zero.

## Output Format
Print a single integer — the required minimum number of visits.

## Examples
```input
3
1 0 0
```
```output
1
```
-----
```input
3
2 0 2
```
```output
6
```
-----
```input
5
0 3 1 3 2
```
```output
14
```
-----
```input
5
1000000000 1000000000 1000000000 1000000000 0
```
```output
4999999999
```

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
Summer in Berland lasts $$$n$$$ days, the price of one portion of ice cream on the $$$i$$$-th day is $$$c_i$$$. Over the summer, Tanya wants to eat exactly $$$k$$$ portions of ice cream. At the same time, on the $$$i$$$-th day, she decided that she would eat at least $$$a_i$$$ portions, but not more than $$$b_i$$$ ($$$a_i \le b_i$$$) portions. In other words, let $$$d_i$$$ be equal to the number of portions that she eats on the $$$i$$$-th day. Then $$$d_1+d_2+\dots+d_n=k$$$ and $$$a_i \le d_i \le b_i$$$ for each $$$i$$$.

Given that portions of ice cream can only be eaten on the day of purchase, find the minimum amount of money that Tanya can spend on ice cream in the summer.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2\cdot10^5$$$, $$$0 \le k \le 10^9$$$) — the number of days and the total number of servings of ice cream that Tanya will eat in the summer.

The following $$$n$$$ lines contain descriptions of the days, one description per line. Each description consists of three integers $$$a_i, b_i, c_i$$$ ($$$0 \le a_i \le b_i \le 10^9$$$, $$$1 \le c_i \le 10^6$$$).

## Output Format
Print the minimum amount of money that Tanya can spend on ice cream in the summer. If there is no way for Tanya to buy and satisfy all the requirements, then print -1.

## Examples
```input
3 7
3 5 6
0 3 4
3 3 3
```
```output
31
```
-----
```input
1 45000
40000 50000 100000
```
```output
4500000000
```
-----
```input
3 100
2 10 50
50 60 16
20 21 25
```
```output
-1
```
-----
```input
4 12
2 5 1
1 2 2
2 3 7
3 10 4
```
```output
35
```

## Note
In the first example, Tanya needs to eat $$$3$$$ portions of ice cream on the first day, $$$1$$$ portions of ice cream on the second day and $$$3$$$ portions of ice cream on the third day. In this case, the amount of money spent is $$$3\cdot6+1\cdot4+3\cdot3=31$$$. It can be shown that any other valid way to eat exactly $$$7$$$ portions of ice cream costs more.

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
There are $$$n$$$ table bowling players, the rating of the $$$i$$$-th player equals $$$r_i$$$. Compose a maximum number of teams in a such way that:

- each player belongs to at most one team;
- each team contains exactly $$$a+b$$$ players;
- each team contains a group of $$$a$$$ players with the same rating and a group of $$$b$$$ players with another same rating, which must be $$$k$$$ times larger than the rating of the players in the first group.

For example, if $$$n=12$$$, $$$r=[1, 1, 2, 2, 2, 2, 2, 3, 3, 4, 6, 6]$$$, $$$a=1$$$, $$$b=2$$$, $$$k=2$$$, you can compose two teams with ratings $$$[1, 2, 2]$$$ and one team with ratings $$$[3, 6, 6]$$$. So, the maximum number of teams is $$$3$$$.

Find the maximum number of teams by given $$$n, r_1 \dots r_n, a, b$$$ and $$$k$$$ to compose in respect to the given requirements.

## Input Format
The first line of the input contains four integers $$$n$$$, $$$a$$$, $$$b$$$ and $$$k$$$ ($$$1 \le n,a,b \le 3\cdot10^5$$$, $$$2 \le k \le 1000$$$). The second line contains the sequence of player's ratings — integers $$$r_1, r_2, \dots, r_n$$$ ($$$1 \le r_i \le 10^6$$$).

## Output Format
Print only one integer — the maximum number of teams that can be composed from $$$n$$$ given players.

## Examples
```input
12 1 2 2
1 1 2 2 2 2 2 3 3 4 6 6
```
```output
3
```
-----
```input
14 1 1 3
3 3 1 1 9 9 2 3 6 6 3 18 3 18
```
```output
6
```
-----
```input
1 2 3 10
1000000
```
```output
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: 5.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarp recently became an employee of the company "Double Permutation Inc." Now he is a fan of permutations and is looking for them everywhere!

A permutation in this problem is a sequence of integers $$$p_1, p_2, \dots, p_k$$$ such that every integer from $$$1$$$ to $$$k$$$ occurs exactly once in it. For example, the following sequences are permutations of $$$[3, 1, 4, 2]$$$, $$$[1]$$$ and $$$[6, 1, 2, 3, 5, 4]$$$. The following sequences are not permutations: $$$[0, 1]$$$, $$$[1, 2, 2]$$$, $$$[1, 2, 4]$$$ and $$$[2, 3]$$$.

In the lobby of the company's headquarter statistics on visits to the company's website for the last $$$n$$$ days are published — the sequence $$$a_1, a_2, \dots, a_n$$$. Polycarp wants to color all the elements of this sequence in one of three colors (red, green or blue) so that:

- all red numbers, being written out of $$$a_1, a_2, \dots, a_n$$$ from left to right (that is, without changing their relative order), must form some permutation (let's call it $$$P$$$);
- all green numbers, being written out of $$$a_1, a_2, \dots, a_n$$$ from left to right (that is, without changing their relative order), must form the same permutation $$$P$$$;
- among blue numbers there should not be elements that are equal to some element of the permutation $$$P$$$.

Help Polycarp to color all $$$n$$$ numbers so that the total number of red and green elements is maximum.

## Input Format
The first line contains an integer $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — the length of the sequence $$$a$$$. The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2\cdot10^5$$$).

## Output Format
Print a string $$$s$$$ of length $$$n$$$ such that:

- $$$s_i$$$='R', if the element $$$a_i$$$ must be colored in red;
- $$$s_i$$$='G', if the element $$$a_i$$$ must be colored in green;
- $$$s_i$$$='B', if the element $$$a_i$$$ must be colored in blue.

The string $$$s$$$ should maximize the total number of red and green elements when fulfilling the requirements from the main part of the problem statement. If there are several optimal answers, print any of them.

## Examples
```input
5
1 2 3 2 1
```
```output
RBBBG
```
-----
```input
3
1 1 1
```
```output
BBB
```
-----
```input
10
3 3 2 2 5 4 1 5 4 1
```
```output
RGRGRRRGGG
```
-----
```input
10
3 9 3 1 2 1 2 4 4 4
```
```output
RBGRRGGBBB
```

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
Polycarp really likes writing the word "kotlin". He wrote this word several times in a row without spaces. For example, he could write the string like "kotlinkotlinkotlinkotlin".

Polycarp sliced (cut) the written string into $$$n$$$ pieces and mixed them. As a result, he has $$$n$$$ strings $$$s_1, s_2, \dots, s_n$$$ and he can arrange them in the right order, concatenate (join) all of them and get a string like "kotlinkotlin...kotlin".

Help Polycarp to find the right order of strings $$$s_1, s_2, \dots, s_n$$$, so that if he writes the strings in this order, he will get the word "kotlin" or the sequence of this word.

Pay attention that you must use all given strings and you must use each string only once.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of Polycarp's strings. Next lines of the input contain $$$n$$$ Polycarp's strings.

Total sum of their lengths doesn't exceed $$$3\cdot10^5$$$. It's guaranteed that there is the right order of arrangement the strings that if you concatenate them into one string, you will get some non-empty sequence of the word "kotlin".

## Output Format
Print $$$n$$$ different integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$), where $$$p_i$$$ is an index of the string that should be the $$$i$$$-th in a required concatenation. In other words, the result of concatenation $$$s_{p_1}+s_{p_2}+\dots+s_{p_n}$$$ must be in the form "kotlinkotlin...kotlin". If there are many solutions, print any of them.

## Examples
```input
2
lin
kot
```
```output
2 1
```
-----
```input
4
linkotlinkotlinkotl
kotlin
in
kot
```
```output
2 4 1 3
```
-----
```input
8
i
n
tlin
o
ko
t
k
l
```
```output
7 4 3 5 6 8 1 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Monocarp has got two strings $$$s$$$ and $$$t$$$ having equal length. Both strings consist of lowercase Latin letters "a" and "b".

Monocarp wants to make these two strings $$$s$$$ and $$$t$$$ equal to each other. He can do the following operation any number of times: choose an index $$$pos_1$$$ in the string $$$s$$$, choose an index $$$pos_2$$$ in the string $$$t$$$, and swap $$$s_{pos_1}$$$ with $$$t_{pos_2}$$$.

You have to determine the minimum number of operations Monocarp has to perform to make $$$s$$$ and $$$t$$$ equal, and print any optimal sequence of operations — or say that it is impossible to make these strings equal.

## Input Format
The first line contains one integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^{5})$$$ — the length of $$$s$$$ and $$$t$$$.

The second line contains one string $$$s$$$ consisting of $$$n$$$ characters "a" and "b".

The third line contains one string $$$t$$$ consisting of $$$n$$$ characters "a" and "b".

## Output Format
If it is impossible to make these strings equal, print $$$-1$$$.

Otherwise, in the first line print $$$k$$$ — the minimum number of operations required to make the strings equal. In each of the next $$$k$$$ lines print two integers — the index in the string $$$s$$$ and the index in the string $$$t$$$ that should be used in the corresponding swap operation.

## Examples
```input
4
abab
aabb
```
```output
2
3 3
3 2
```
-----
```input
1
a
b
```
```output
-1
```
-----
```input
8
babbaabb
abababaa
```
```output
3
2 6
1 3
7 8
```

## Note
In the first example two operations are enough. For example, you can swap the third letter in $$$s$$$ with the third letter in $$$t$$$. Then $$$s = $$$ "abbb", $$$t = $$$ "aaab". Then swap the third letter in $$$s$$$ and the second letter in $$$t$$$. Then both $$$s$$$ and $$$t$$$ are equal to "abab".

In the second example it's impossible to make two strings equal.

Now solve the problem and return the code.