# An interesting game challenge

**Problem statement**

Andy loves playing games. He wants to play a game with his little brother, Bob, using an array, , of distinct integers. The rules are as follows:

- Bob always plays first and the two players move in alternating turns.
- In a single move, a player chooses the maximum element currently present in the array and removes it as well as all the other elements to its right. For example, if , then it becomes after the first move because we remove the maximum element (i.e., ) and all elements to its right (i.e., and ).
- The modifications made to the array during each turn are permanent, so the next player continues the game with the remaining array. The first player who is unable to make a move loses the game.

Andy and Bob play games. Given the initial array for each game, can you find and print the name of the winner on a new line? If Andy wins, print `ANDY`

; if Bob wins, print `BOB`

.

**Input Format**

The first line contains a single integer denoting (the number of games). The subsequent lines describe each game array over two lines:

- The first line contains a single integer, , denoting the number of elements in .
- The second line contains distinct space-separated integers describing the respective values of for array .

**Constraints**

Array contains distinct integers.

The sum of over all games does not exceed .

**Output Format**

For each game, print the name of the winner on a new line (i.e., either `BOB`

or `ANDY`

).

**Sample Input 0**

2 5 5 2 6 3 4 2 3 1

**Sample Output 0**

ANDY BOB

**Explanation 0**

Andy and Bob play the following two games:

1.

Initially, the array looks like this:

In the first move, Bob removes and all the elements to its right, resulting in :

In the second move, Andy removes and all the elements to its right, resulting in :

At this point, the array is empty and Bob cannot make any more moves. This means Andy wins, so we print `ANDY`

on a new line.

2.

In the first move, Bob removes and all the elements to its right, resulting in . As there are no elements left in the array for Andy to make a move, Bob wins and we print `BOB`

on a new line.

**Solution**

public class AnInterestingGame { private static final String BOB = "BOB"; private static final String ANDY = "ANDY"; private static void solve(int[] a, int start, int end, String player) { if (start > end) { System.out.println(player.equals(BOB) ? ANDY : BOB); } else { int max = Integer.MIN_VALUE; int maxIdx = -1; for (int i = start; i <= end; i++) { if (a[i] > max) { max = a[i]; maxIdx = i; } } solve(a, start, maxIdx - 1, player.equals(BOB) ? ANDY : BOB); } } public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt")); Scanner in = new Scanner(System.in); int games = in.nextInt(); for (int g = 0; g < games; g++) { int n = in.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = in.nextInt(); } solve(a, 0, a.length - 1, BOB); } } }