A12013 | 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 > 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.

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$ .

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".