Polycarp 最近成为“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$$$。 Polycarp 希望用三种颜色(红色、绿色或蓝色)之一为该序列的所有元素着色,以便:
- 所有红色数字,从左到右从 $$$a_1, a_2, \dots, a_n$$$ 写出(即不改变它们的相对顺序),必须形成某种排列(我们称之为 $$$P$$$);
- 所有绿色数字,从左到右从 $$$a_1, a_2, \dots, a_n$$$ 写出(即,不改变它们的相对顺序),必须形成相同的排列 $$$P$$$;
- 在蓝色数字中不应存在等于排列 $$$P$$$ 的某些元素的元素。
帮助Polycarp为所有$$$n$$$数字着色,使红色和绿色元素的总数最大。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — 序列 $$$a$$$ 的长度。第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2\cdot10^5$$$)。
输出
打印长度为 $$$n$$$ 的字符串 $$$s$$$,使得:
- $$$s_i$$$='R',如果元素 $$$a_i$$$ 必须为红色;
- $$$s_i$$$='G',如果元素 $$$a_i$$$ 必须为绿色;
- $$$s_i$$$='B',如果元素 $$$a_i$$$ 必须为蓝色。
当满足问题陈述主要部分的要求时,字符串 $$$s$$$ 应最大化红色和绿色元素的总数。如果有多个最佳答案,请打印其中任何一个。
示例
输入 #1
5 1 2 3 2 1
输出 #1
RBBBG
输入 #2
3 1 1 1
输出 #2
BBB
输入 #3
10 3 3 2 2 5 4 1 5 4 1
输出 #3
RGRGRRRGGG
输入#4
10 3 9 3 1 2 1 2 4 4 4
输出#4
RBGRRGGBBB