Double Permutation Inc - VietMX's Blog

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

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

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

Solution:

private fun readLn() = readLine()!! // string line
private fun readInt() = readLn().toInt() // single int
private fun readLong() = readLn().toLong() // single long
private fun readDouble() = readLn().toDouble() // single double
private fun readStrings() = readLn().split(" ") // list of strings
private fun readInts() = readStrings().map { it.toInt() } // list of ints
private fun readLongs() = readStrings().map { it.toLong() } // list of longs
private fun readDoubles() = readStrings().map { it.toDouble() } // list of doubles
 
fun main(args: Array<String>) {
var n = readInt()
var a = readInts()
val MAX = 200010
var cnt = IntArray(MAX)
for (x in a) cnt[x]++
var low = 0
var high = n
while (low < high) {
        var mid = (low + high + 1) / 2
        var ok = true
        for (i in 1..mid) {
            if (cnt[i] != 2) {
                ok = false
                break
            }
        }
        if (ok) {
            var x = ArrayList<Int>()
var y = 0
var cc = IntArray(mid + 1)
for (v in a) {
if (v <= mid) {
                    if (cc[v] == 0) {
                        x.add(v)
                    } else {
                        if (x[y] != v) {
                            ok = false
                            break
                        }
                        y += 1
                    }
                    cc[v] += 1
                }
            }
        }
        if (ok) {
            low = mid
        } else {
            high = mid-1
        }
    }
    var res = CharArray(n)
    var mid = low
        var x = ArrayList<Int>()
var y = 0
var cc = IntArray(mid + 1)
for (it in 0..n-1) {
var v = a[it]
if (v <= mid) {
                if (cc[v] == 0) {
                    res[it] = 'R'
                } else {
                    res[it] = 'G'
                }
                cc[v] += 1
            } else {
                res[it] = 'B'
            }
        }
    println(res.joinToString(""))
}