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

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.