Недавно Поликарп стал сотрудником компании «Double Permutation Inc.» Теперь он фанатеет от перестановок и всюду их ищет!
Перестановкой в этой задаче будем называть такую последовательность целых чисел \(p_1, p_2, \dots, p_k\), что каждое целое число от \(1\) до \(k\) встречается в ней ровно один раз. Например, следующие последовательности являются перестановками \([3, 1, 4, 2]\), \([1]\) и \([6, 1, 2, 3, 5, 4]\). Следующие последовательности не являются перестановками: \([0, 1]\), \([1, 2, 2]\), \([1, 2, 4]\) и \([2, 3]\).
В холле штаб-квартиры компании опубликована статистика посещения веб-сайта компании за последние \(n\) дней — последовательность \(a_1, a_2, \dots, a_n\). Поликарп хочет покрасить все элементы этой последовательности один из трёх цветов (красный, зеленый или синий) так, что:
- все красные числа, будучи выписанными из \(a_1, a_2, \dots, a_n\) слева направо (то есть без изменения их относительного порядка), должны образовывать некоторую перестановку (назовём её \(P\));
- все зеленые числа, будучи выписанными из \(a_1, a_2, \dots, a_n\) слева направо (то есть без изменения их относительного порядка), должны образовывать туже самую перестановку \(P\);
- среди синих чисел не должно быть элементов, которые равны некоторому элементу перестановки \(P\).
Помогите Поликарпу покрасить все \(n\) чисел так, чтобы суммарное количество красных и зеленых элементов было максимально.
Выходные данные
Выведите строку \(s\) длины \(n\) такую, что:
- \(s_i\)='R', если элемент \(a_i\) должен быть покрашен в красный цвет;
- \(s_i\)='G', если элемент \(a_i\) должен быть покрашен в зеленый цвет;
- \(s_i\)='B', если элемент \(a_i\) должен быть покрашен в синий цвет.
Строка \(s\) должна максимизировать суммарное количество красных и зелёных элементов при выполнении требований из основной части условия задачи. Если оптимальных ответов несколько, то выведите любой из них.