H. Asteroid Trek
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Jesse and Jerry are in outer space! Unfortunately, they have gotten lost and ended up on either side of a huge asteroid range.

There are $$$n$$$ asteroids in a row, numbered $$$1, 2, \ldots, n$$$. The $$$i$$$-th asteroid from the left has a size $$$s_i$$$.

Jesse starts to the left of asteroid $$$1$$$, and Jerry starts to the right of asteroid $$$n$$$. They are both floating in space, so we say that they start standing on asteroids of size $$$0$$$.

Jesse always wants to outdo Jerry, so he is only happy if he's standing on an asteroid at least as large as the one Jerry's standing on. Formally, if Jesse is standing on asteroid $$$a$$$ and Jerry is standing on asteroid $$$b$$$, Jesse is only happy if $$$s_b \le s_a$$$.

They also want to stand on the same asteroid (they need to plan CerealCodes!). To help them, you are allowed to send them instructions, each consisting of a single character:

  • A: tell Jesse to move to the asteroid on his right;
  • B: tell Jerry to move to the asteroid on his left.

You will send them these instructions as a string of length $$$n+1$$$, consisting of the letters A and B.

Find the lexicographically maximum string of instructions that brings Jesse and Jerry together while keeping Jesse happy at all times.

A string $$$s$$$ of length $$$n+1$$$ is lexicographically greater than a string $$$t$$$ of length $$$n+1$$$ if and only if the following holds:

  • in the first position where $$$s$$$ and $$$t$$$ differ, the string $$$s$$$ has a letter that appears later in the alphabet than the corresponding letter in $$$t$$$.
Input

There will be $$$t$$$ ($$$1 \leq t \leq 1000$$$) independent test cases.

The first line of each test case contains $$$n$$$, the number of asteroids ($$$1 \le n \le 5000$$$).

The second line of each test case contains $$$n$$$ integers $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \le s_i \le 10^9$$$)  — the sizes of the asteroids.

The sum of $$$n$$$ over all test cases will not exceed $$$5000$$$.

Output

For each test case, print a string of length $$$n+1$$$, representing the lexicographically maximum sequence of instructions satisfying the conditions above.

Example
Input
2
7
5 2 6 5 3 4 1
1
1
Output
ABAABBBB
AB
Note

Here is the optimal path of traversal:

  • First, Jesse moves to asteroid $$$1$$$. $$$0 \le a_1$$$, so Jesse is happy;
  • Next, Jerry moves to asteroid $$$7$$$. $$$a_7 \le a_1$$$, so Jesse is happy;
  • Jesse then moves to asteroid $$$2$$$. $$$a_7 \le a_2$$$, so Jesse is happy;
  • Jesse moves again to asteroid $$$3$$$. $$$a_7 \le a_3$$$, so Jesse is happy.
Finally, Jerry moves left $$$4$$$ times and comes to asteroid $$$3$$$. Jesse stays happy because $$$a_i \le a_3$$$ for $$$3 \le i \le 7$$$.

Problem Credits: Mythreya Dharani and Eric Hsu