Double Permutation Inc.
Contest: Kotlin Heroes: Episode 2
Difficulty rating: 2000
Tags: *special, binary search, greedy

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.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Example input:
5
1 2 3 2 1

Example output:
RBBBG

Example input:
3
1 1 1

Example output:
BBB

Editorial:
One can solve the problem with binary search by the length of a permutation. If the length is $$$len$$$ then:
• just ignore all elements greater than $$$len$$$ (paint the with blue);
• the expected number of unpainted elements is $$$2 \cdot len$$$: two $$$1$$$'s, two $$$2$$$'s and so on;
• split the into two permutations with a greedy approach and check that they are equal.
If it is impossible to process any item above, it means that there is no solution with the length of a permutation that equals $$$len$$$.
There is an alternative solution without any binary search. You can greedily construct both permutations in order: add into them elements that equal $$$1$$$, add into them elements that equal $$$2$$$ and so on. Before the step $$$i$$$ you should check that there are exactly two occurrences of $$$i$$$ in the given array. After each step you should check that the current two permutations are equal. You can easily check it if you maintain them as ordered maps and each time you insert new elements at the same positions (the code below checks that next elements after the inserted are the same).
Here is the example of a solution in Kotlin: