После долгого дня Алиса и Боб решили сыграть в игру. Игровая доска состоит из $$$n$$$ ячеек на прямой, пронумерованных от $$$1$$$ до $$$n$$$, где каждая ячейка содержит число $$$a_i$$$ в диапазоне от $$$1$$$ до $$$n$$$. Кроме того, никакие две ячейки не содержат одинаковые числа.
Игровая фигурка находится на одной ячейке. Они ходят по очереди, двигая фигурку. Алиса ходит первая. Игрок, который ходит, может передвинуть фигурку с ячейки $$$i$$$ на ячейку $$$j$$$, только если выполняются условия:
Проигрывает тот, кто не может сделать ход. Для каждой начальной позиции нужно определить, кто победит при оптимальной игре обоих. Можно доказать, что игра всегда когда-нибудь закончится, то есть всегда есть оптимальная стратегия для одного игрока.
Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество чисел.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$). Гарантируется, что нет таких чисел $$$i \neq j$$$, что $$$a_i = a_j$$$.
Выведите $$$s$$$ — строку из $$$n$$$ символов, где $$$i$$$-й символ представляет результат игры, которая начинается в ячейке $$$i$$$. Если победит Алиса, то $$$s_i$$$ должен быть равен «A»; в другом случае, $$$s_i$$$ должен быть равен «B».
8
3 6 5 4 2 7 1 8
BAAAABAB
15
3 11 2 5 10 9 7 13 15 8 4 12 6 1 14
ABAAAABBBAABAAB
В первом примере, если Боб поместит игровую фигурку на число (не на позицию):
Название |
---|