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:
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".
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
In the first sample, if Bob puts the token on the number (not position):
Name |
---|