C. Игра с перестановкой
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После долгого дня Алиса и Боб решили сыграть в игру. Игровая доска состоит из $$$n$$$ ячеек на прямой, пронумерованных от $$$1$$$ до $$$n$$$, где каждая ячейка содержит число $$$a_i$$$ в диапазоне от $$$1$$$ до $$$n$$$. Кроме того, никакие две ячейки не содержат одинаковые числа.

Игровая фигурка находится на одной ячейке. Они ходят по очереди, двигая фигурку. Алиса ходит первая. Игрок, который ходит, может передвинуть фигурку с ячейки $$$i$$$ на ячейку $$$j$$$, только если выполняются условия:

  • число в новой ячейке $$$j$$$ строго больше, чем в старой ячейке $$$i$$$ (то есть $$$a_j > a_i$$$), и
  • расстояние, на которое передвигается фигурка в этом ходу, должно делиться на число, расположенное в старой ячейке (то есть $$$|i-j|\bmod a_i = 0$$$).

Проигрывает тот, кто не может сделать ход. Для каждой начальной позиции нужно определить, кто победит при оптимальной игре обоих. Можно доказать, что игра всегда когда-нибудь закончится, то есть всегда есть оптимальная стратегия для одного игрока.

Входные данные

Первая строка содержит одно целое число $$$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
Примечание

В первом примере, если Боб поместит игровую фигурку на число (не на позицию):

  • $$$1$$$: Алиса может переместиться на любую ячейку. Она может выбрать число $$$7$$$, из которого у Боба нет выхода.
  • $$$2$$$: Алиса может переместиться на числа $$$3$$$ и $$$5$$$. При переходе в $$$5$$$, Боб может выиграть, если переместится в $$$8$$$. Если она выберет $$$3$$$, то она победит, так как Боб сможет переместиться только в $$$4$$$, из которого Алиса сможет переместиться в $$$8$$$.
  • $$$3$$$: Алиса может переместиться только в $$$4$$$, после чего Боб побеждает, перемещаясь в $$$8$$$.
  • $$$4$$$, $$$5$$$ или $$$6$$$: Алиса побеждает, перемещаясь в $$$8$$$.
  • $$$7$$$, $$$8$$$: Алиса не может никуда переместиться, поэтому проигрывает.