TX202610 彩珠展示带

题目描述

美术社有 N 颗彩珠，每颗彩珠的颜色用一个大写英文字母表示，相同字母表示相同颜色。

同学们准备将所有彩珠重新排列，制作一条展示带。

展示带是一条直线，首尾不相接。为了让颜色搭配更加丰富，任意两颗相邻彩珠的颜色都不能相同。

在所有符合要求的排列中，同学们希望得到字典序最小的一种。

请你重新排列这些彩珠。如果无法得到符合要求的排列，输出 -1。

你必须使用全部彩珠，并且每种颜色的使用数量必须与原来相同。

对于两个长度相同但不完全相同的字符串，从左到右找到第一个不同的位置，该位置字母较小的字符串字典序较小。字母顺序为：

A < B < C < ... < Z

输入格式

第一行包含一个正整数 N，表示彩珠数量。

第二行包含一个长度为 N 的字符串 S，只包含大写英文字母，表示所有彩珠的颜色。

输出格式

如果存在合法排列，输出字典序最小的合法字符串。

否则输出 -1。

样例 1 输入

6
AAABBC

样例 1 输出

ABABAC

样例 1 说明

输出使用了三颗 A、两颗 B 和一颗 C，且任意两颗相邻彩珠的颜色都不同。

不存在字典序更小的合法排列。

样例 2 输入

4
AAAB

样例 2 输出

-1

样例 2 说明

无论如何排列，都会出现两颗颜色为 A 的彩珠相邻。

数据范围

• 1 ≤ N ≤ 10^5
• S 的长度为 N
• S 只包含 A 至 Z

子任务如下，各子任务独立计分：