Little Alice and Little Bob are playing with their favourite toys, Lego blocks. They have N blocks of various heights, arranged in a row. They decide to play a game with their blocks.
Alice and Bob take turns removing one Lego block from the row, with Alice going first. At the beginning of a player’s turn, if the blocks form a ladder - a sequence of either non-increasing or non-decreasing heights - that player loses. Given the heights of the initial row of blocks, determine who has the winning strategy, if they play optimally.
The input file DATA4.txt will contain 5 test cases, and each test case describes 3 games. The first line of each game contains a number N (1 ≤ N ≤ 15), the number of blocks in that game. The next line contains N space-separated integers, representing the heights of the blocks, which will be integers from 0 to 100 inclusive.
The output file OUT4.txt will contain 5 lines, with strings of 3 characters each. The ith character of the jth line should represent the result of the ith game of the jth test case: ‘A’ if Little Alice wins, and ‘B’ if Little Bob wins.
2 2 3 3 0 2 2 4 1 2 4 3