CF1033C.Permutation Game

After a long day, Alice and Bob decided to play a little game. The game board consists of $n$ cells in a straight line, numbered from $1$ to $n$, where each cell contains a number $a_i$ between $1$ and $n$. Furthermore, no two cells contain the same number.

A token is placed in one of the cells. They take alternating turns of moving the token around the board, with Alice moving first. The current player can move from cell $i$ to cell $j$ only if the following two conditions are satisfied:

• the number in the new cell $j$ must be strictly larger than the number in the old cell $i$ (i.e. $a_j \gt a_i$), and
• the distance that the token travels during this turn must be a multiple of the number in the old cell (i.e. $|i-j|\bmod a_i = 0$).

Whoever is unable to make a move, loses. For each possible starting position, determine who wins if they both play optimally. It can be shown that the game is always finite, i.e. there always is a winning strategy for one of the players.

经过漫长的一天后，Alice 和 Bob 决定玩一个小游戏。游戏棋盘由一行 $n$ 个格子组成，编号从 $1$ 到 $n$，每个格子中包含一个介于 $1$ 到 $n$ 之间的整数 $a_i$。此外，任意两个格子中的数字互不相同。

一个棋子被放置在某个格子中。他们轮流移动该棋子，Alice 先手。当前玩家可以从格子 $i$ 移动到格子 $j$，当且仅当满足以下两个条件：

• 新格子 $j$ 中的数字必须严格大于旧格子 $i$ 中的数字（即 $a_j > a_i$），且
• 本次移动的距离必须是旧格子中数字的倍数（即 $|i-j| \bmod a_i = 0$）。

无法进行合法移动的一方判负。对每个可能的起始位置，请判断若双方均以最优策略进行游戏，谁将获胜。可以证明该游戏总是有限的，即总有一方存在必胜策略。

The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of numbers.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$). Furthermore, there are no pair of indices $i \neq j$ such that $a_i = a_j$.

第一行包含一个整数 $n$（$1 \le n \le 10^5$）—— 数字的个数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）。此外，不存在满足 $a_i = a_j$ 的下标对 $i \neq j$。

Print $s$ — a string of $n$ characters, where the $i$-th character represents the outcome of the game if the token is initially placed in the cell $i$. If Alice wins, then $s_i$ has to be equal to "A"; otherwise, $s_i$ has to be equal to "B".

输出字符串 $s$ —— 一个长度为 $n$ 的字符串，其中第 $i$ 个字符表示当棋子初始放置在第 $i$ 个格子时游戏的结果：若爱丽丝获胜，则 $s_i$ 应为 "A"；否则 $s_i$ 应为 "B"。

In the first sample, if Bob puts the token on the number (not position):

• $1$: Alice can move to any number. She can win by picking $7$, from which Bob has no move.
• $2$: Alice can move to $3$ and $5$. Upon moving to $5$, Bob can win by moving to $8$. If she chooses $3$ instead, she wins, as Bob has only a move to $4$, from which Alice can move to $8$.
• $3$: Alice can only move to $4$, after which Bob wins by moving to $8$.
• $4$, $5$, or $6$: Alice wins by moving to $8$.
• $7$, $8$: Alice has no move, and hence she loses immediately.

在第一个样例中，如果 Bob 将棋子放在某个数字（而非位置）上：

• $1$：Alice 可以移动到任意数字。她可以选择 $7$，此时 Bob 无法移动，从而获胜。
• $2$：Alice 可以移动到 $3$ 或 $5$。若她移动到 $5$，则 Bob 可通过移动到 $8$ 获胜；若她改为移动到 $3$，则她获胜，因为 Bob 此时只能移动到 $4$，而 Alice 接着可从 $4$ 移动到 $8$。
• $3$：Alice 只能移动到 $4$，随后 Bob 通过移动到 $8$ 获胜。
• $4$、$5$ 或 $6$：Alice 通过移动到 $8$ 获胜。
• $7$、$8$：Alice 无法移动，因此立即失败。