Andy wants to play a game with his little brother, Bob.  The game starts with an array of distinct integers and the rules are as follows:

Bob always plays first.   
In a single move, a player chooses the maximum element in the array.  He removes it and all elements to its right. For example, if the starting array $arr=[2,3,5,4,1]$, then it becomes $ar r'=[2,3]$ after removing $[5,4,1]$.  
The two players alternate turns. 
The last player who can make a move wins.  

Andy and Bob play $\mathrm{~g~}$ games. Given the initial array for each game, find and print the name of the winner on a new line. If Andy wins, print ANDY; if Bob wins, print BOB.

To continue the example above, in the next move Andy will remove $3$.  Bob will then remove $2$ and win because there are no more integers to remove.  

Function Description  

Complete the gamingArray function in the editor below.  

gamingArray has the following parameter(s):  

int arr[n]: an array of integers   

Returns 

- string: either ANDY or BOB  

Input Format

The first line contains a single integer $\mathrm{~g~}$, the number of games.

Each of the next $\mathrm{~g~}$ pairs of lines is as follows:

The first line contains a single integer, $n$, the number of elements in $\textbf{arr}$.
The second line contains $n$ distinct space-separated integers $arr\left[i\right]$ where $0\leq i<n$.  

Constraints

Array $\textbf{arr}$ contains $n$ distinct integers.

For $35\%$ of the maximum score:

$1\leq g\leq10$  
$1\leq n\leq1000$  
$1\leq ar r[i]\leq10^5$    
The sum of $n$ over all games does not exceed $\textbf{1000}$.

For $\textbf{100\%}$ of the maximum score:

$1\leq g\leq100$  
$1\leq n\leq10^5$  
$1\leq a_i\leq10^9$  
The sum of $n$ over all games does not exceed $10^{5}$.

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:

Initially, the array looks like this: 

In the first move, Bob removes $\boldsymbol{6}$ and all the elements to its right, resulting in $A=[5,2]$: 

In the second move, Andy removes $5$ and all the elements to its right, resulting in $A=\left[\right]$: 

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.

In the first move, Bob removes $3$ and all the elements to its right, resulting in $A=\left[\right]$. 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.

Sample Input 1
2
5
1 3 5 7 9
5
7 4 6 5 9

Sample Output 1
BOB
ANDY

Explanation 1

In the first test, they alternate choosing the rightmost element until the end.  Bob, Andy, Bob, Andy, Bob.  

In the second case, Bob takes $\mbox{9}$, Andy takes $[7,4,6,5]$.

Source: hackerrank | Difficulty: MEDIUM
Tags: Constructive algorithms


Solutions:
import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	a = list(map(int, input().split()))
	idx_sorted = [x for (x, y) in sorted(enumerate(a), key=lambda x: -x[1])]
	max_idx = n
	bob_wins = False
	for i in range(n):
		idx = idx_sorted[i]
		if idx < max_idx:
			max_idx = idx
			bob_wins = not bob_wins
	if bob_wins:
		print('BOB')
	else:
		print('ANDY')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	a = list(map(int, input().split()))
	maxtotheleft = []
	curmaxidx = None
	for i in range(n):
		if curmaxidx == None or a[curmaxidx] < a[i]:
			curmaxidx = i
		maxtotheleft.append(curmaxidx)
	curplayer = True
	for i in reversed(range(n)):
		if maxtotheleft[i] == i:
			curplayer = not curplayer
	if curplayer:
		print('ANDY')
	else:
		print('BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	a = [int(x) for x in input().split(' ')]
	turns = 0
	target = 0
	highest = 0
	for v in a:
		if v > target and v > highest:
			highest = v
			turns += 1
		target = v
	print('BOB' if turns % 2 == 1 else 'ANDY')


import sys
from operator import itemgetter
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	b = sorted(enumerate(a), key=itemgetter(1), reverse=True)
	m = n
	andy = True
	for i in map(itemgetter(0), b):
		if i > m:
			continue
		m = i
		andy = not andy
	print('ANDY' if andy else 'BOB')


T = int(input().strip())
for t in range(T):
	n = int(input().strip())
	arr = list(map(int, input().strip().split()))
	count = 1
	mx = arr[0]
	for i in range(1, n):
		if arr[i] > mx:
			count += 1
			mx = arr[i]
	if not count & 1:
		print('ANDY')
	else:
		print('BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	xs = [int(x) for x in input().split()]
	maxs = [None for x in xs]
	maxs[0] = (xs[0], 0)
	for i in range(1, len(xs)):
		if xs[i] > maxs[i - 1][0]:
			maxs[i] = (xs[i], i)
		else:
			maxs[i] = maxs[i - 1]
	player = 0
	i = len(xs) - 1
	while i >= 0:
		i = maxs[i][1] - 1
		player ^= 1
	if player == 0:
		print('ANDY')
	else:
		print('BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	arr = [int(i) for i in input().strip().split()]
	cnt = 0
	max = -1
	for i in arr:
		if i > max:
			max = i
			cnt += 1
	if cnt % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	a = list(map(int, input().split()))
	m = a[0]
	nm = 1
	for i in range(n):
		if a[i] > m:
			m = a[i]
			nm += 1
	if nm % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	m = [a[0]]
	for i in range(1, n):
		if a[i] > m[-1]:
			m.append(a[i])
	if len(m) % 2:
		return 'BOB'
	return 'ANDY'
for i in range(int(input())):
	print(solve())


inf = float('inf')
read_ints = lambda : list(map(int, input().split()))

def solve(N, arr):
	arr2 = [(x, i) for (i, x) in enumerate(arr)]
	arr2.sort(reverse=True)
	vis = set()
	last = N
	player = 0
	for (n, pos) in arr2:
		if n not in vis:
			for j in range(pos, last):
				vis.add(arr[j])
			last = pos
			player = (player + 1) % 2
	if player == 0:
		print('ANDY')
	else:
		print('BOB')
T = int(input())
for _ in range(T):
	N = int(input())
	arr = read_ints()
	solve(N, arr)


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	values = input().strip().split()
	values = [int(x) for x in values]
	group = 1
	maximum = values[0]
	for i in range(1, len(values)):
		if values[i] > maximum:
			group = group + 1
			maximum = values[i]
	if group & 1 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	narr = [int(x) for x in input().strip().split()]
	currMax = 0
	count = 0
	for i in narr:
		if i > currMax:
			currMax = i
			count += 1
	if count % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	L = list(map(int, input().split()))
	pl = 1
	M = [(L[i], i) for i in range(len(L))]
	M = sorted(M, key=lambda x: x[0], reverse=True)
	i = 0
	mn = len(M)
	while i < int(len(M)):
		if mn > M[i][1]:
			pl = 1 - pl
		mn = min(mn, M[i][1])
		i += 1
	print('BOB' if pl == 0 else 'ANDY')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	array = [int(x) for x in input().split(' ')]
	filtered_array = []
	max_element = 0
	for current_element in array:
		if max_element > current_element:
			pass
		else:
			filtered_array.append(current_element)
			max_element = current_element
	player_turn_at_last_move = len(filtered_array) % 2
	if player_turn_at_last_move == 0:
		print('ANDY')
	else:
		print('BOB')


games = int(input().strip())
for game in range(games):
	n = int(input().strip())
	values = map(int, input().strip().split(' '))
	flips = 0
	last = -1
	for value in values:
		if value > last:
			flips += 1
			last = value
	if flips % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	A = list(map(int, input().split()))
	m = 0
	c = 0
	for a in A:
		if a > m:
			c += 1
			m = a
	if c % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


from heapq import heappush, heappop

def readInts():
	return map(int, input().strip().split())

def count_removes(n, a):
	h = []
	for (i, ai) in enumerate(a):
		heappush(h, (-ai, i))
	steps = 0
	ix = n
	while h:
		(_, hix) = heappop(h)
		if hix < ix:
			ix = hix
			steps += 1
	return steps
(g,) = readInts()
for _ in range(g):
	(n,) = readInts()
	a = readInts()
	s = count_removes(n, a)
	if s % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	A = [int(num) for num in input().split()]
	M = [0] * n
	for i in range(1, n):
		M[i] = i if A[i] > A[M[i - 1]] else M[i - 1]
	i = n - 1
	cnt = 0
	while i >= 0:
		i = M[i] - 1
		cnt += 1
	if cnt % 2 == 1:
		print('BOB')
	else:
		print('ANDY')


import sys
Games = int(input().strip())
if Games > 100:
	Games = 100

def PlayerMove(board):
	b = sorted(board)
	lg = b[-1]
	if lg > 10 ** 9:
		lg = 10 ** 9
	index = board.index(lg)
	return board[:index]
for Game in range(Games):
	v = int(input().strip())
	board = []
	b = input().split(' ')
	if len(b) > 10 ** 5:
		b = b[:10 ** 5]
	for index in range(len(b)):
		ar = []
		ar.append(index)
		ar.append(int(b[index]))
		board.append(ar)
	moves = 1
	board = sorted(board, key=lambda a: a[1], reverse=True)
	index = board[0][0] + 1
	for i in range(len(board)):
		if board[i][0] < index:
			index = board[i][0]
			moves += 1
		if board[i][0] == 0:
			break
	if moves & 1:
		print('ANDY')
	else:
		print('BOB')


import sys
cases = int(input().strip())
for c in range(cases):
	n = int(input())
	A = list(map(int, input().split()))
	player = 1
	temp = A[0]
	for i in range(len(A)):
		if A[i] > temp:
			temp = A[i]
			player += 1
	if player % 2 != 0:
		print('BOB')
	else:
		print('ANDY')


winner = 'ANDY'

def toggle_winner():
	global winner
	if winner == 'BOB':
		winner = 'ANDY'
	else:
		winner = 'BOB'

def reset_winner():
	global winner
	winner = 'ANDY'

def scan_for_winner(arr):
	global winner
	cur_maxima = 0
	for a in arr:
		if a > cur_maxima:
			cur_maxima = a
			toggle_winner()
	print(winner)
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	arr = list(map(int, input().split()))
	reset_winner()
	scan_for_winner(arr[0:n])


g = int(input().strip())
for _ in range(g):
	n = int(input().strip())
	A = [int(a) for a in input().strip().split(' ')]
	if sorted(A) == A:
		print('ANDY' if len(A) % 2 == 0 else 'BOB')
	else:
		game_play = 0
		while len(A) != 0:
			max_ = max(A)
			new_A = A[:A.index(max(A))]
			A = new_A
			game_play += 1
		print('ANDY' if game_play % 2 == 0 else 'BOB')


import sys

def preparePositionMap(position_list):
	position_map = {}
	iCount = 0
	for element in position_list:
		position_map[element] = iCount
		iCount += 1
	return position_map
test_count = int(input().strip())
for _ in range(test_count):
	arr_size = int(input().strip())
	position_list = list(map(int, input().strip().split(' ')))
	if sorted(position_list) == position_list:
		print('ANDY' if len(position_list) % 2 == 0 else 'BOB')
		continue
	position_map = preparePositionMap(position_list)
	current_chance = 1
	while len(position_list) != 0:
		max_value_index = position_map[max(position_list)]
		position_list = position_list[:max_value_index]
		current_chance = 2 if current_chance == 1 else 1
	if current_chance == 2:
		print('BOB')
	else:
		print('ANDY')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	a = [int(temp) for temp in input().strip().split(' ')]
	c = 1
	m = a[0] - 1
	for ai in a:
		if ai > m:
			m = ai
			c += 1
	if c % 2 == 0:
		print('BOB')
	else:
		print('ANDY')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	prev = 0
	count = 0
	for ai in a:
		if ai > prev:
			count += 1
			prev = ai
	if count % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys

def playcount(A):
	lst = sorted(((a, ix) for (ix, a) in enumerate(A)))
	count = 0
	ix = len(lst) - 1
	while ix >= 0:
		(maxa, maxix) = lst[ix]
		newix = ix - 1
		while newix >= 0:
			(a, ix) = lst[newix]
			if ix < maxix:
				break
			newix -= 1
		ix = newix
		count += 1
	return count
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	A = map(int, input().split())
	if playcount(A) % 2:
		print('BOB')
	else:
		print('ANDY')


import sys

def winner(a):
	c = 1
	d = a[0]
	for x in a[1:]:
		if x > d:
			c += 1
			d = x
	return c % 2 != 0
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	print(winner(a) and 'BOB' or 'ANDY')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	arr = list(map(int, input().split(' ')))
	count = 0
	max_val = 0
	for i in range(n):
		if arr[i] > max_val:
			count += 1
			max_val = arr[i]
	if count % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


for _ in range(int(input())):
	r = n = int(input())
	data = sorted(((int(c), i) for (i, c) in enumerate(input().split())))
	turns = 0
	while n:
		r = data[n - 1][1]
		turns += 1
		n -= 1
		while n and data[n - 1][1] > r:
			n -= 1
	print('BOB' if turns % 2 else 'ANDY')


import sys
g = int(input().strip())
for _ in range(g):
	n = int(input().strip())
	A = [int(a) for a in input().strip().split(' ')]
	if sorted(A) == A:
		print('ANDY' if len(A) % 2 == 0 else 'BOB')
	else:
		game_play = 0
		while len(A) != 0:
			new_A = A[:A.index(max(A))]
			A = new_A
			game_play += 1
		print('ANDY' if game_play % 2 == 0 else 'BOB')


import sys
g = int(input())
for _ in range(g):
	n = int(input())
	if n > 0:
		arr = [int(x) for x in input().split()]
		bob_wins = True
		tmp = arr[0]
		for i in range(1, n):
			if arr[i] > tmp:
				tmp = arr[i]
				bob_wins = not bob_wins
	if bob_wins:
		print('BOB')
	else:
		print('ANDY')


import sys

def prefix_maxima_count(arr):
	count = 1
	max_val = arr[0]
	for i in arr:
		if i > max_val:
			count += 1
			max_val = i
	return count

def first_wins(arr):
	return prefix_maxima_count(arr) % 2 == 1
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	arr = list(map(int, input().split()))
	print('BOB' if first_wins(arr) else 'ANDY')


import sys

def solve(aa):

	def get_max_cache():
		max_cache = [0]
		for i in range(1, len(aa)):
			ix = max_cache[-1]
			if aa[i] > aa[ix]:
				ix = i
			max_cache.append(ix)
		return max_cache
	max_cache = get_max_cache()
	cnt = 0
	i = len(aa)
	while i != 0:
		i = max_cache[i - 1]
		cnt += 1
	return cnt % 2 == 0
t = int(input())
for _ in range(t):
	_ = int(input())
	aa = list(map(int, input().split()))
	if solve(aa):
		print('ANDY')
	else:
		print('BOB')


import sys

def winner(a):
	c = 0
	while a:
		x = a.index(max(a))
		a = a[:x]
		c += 1
	print(['ANDY', 'BOB'][c % 2 != 0])
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	a = list(map(int, input().split()))
	if sorted(a) == a:
		print(['ANDY', 'BOB'][n % 2 != 0])
	else:
		winner(a)


for _ in range(int(input().strip())):
	n = int(input().strip())
	data = list(map(int, input().split()))
	s = set()
	m = data[0]
	for i in data:
		m = max(m, i)
		s.add(m)
	print('BOB' if len(s) % 2 == 1 else 'ANDY')


g = int(input().strip())
for _ in range(g):
	n = int(input().strip())
	A = [int(a) for a in input().strip().split(' ')]
	if sorted(A) == A:
		print('ANDY' if len(A) % 2 == 0 else 'BOB')
	else:
		game_play = 0
		while len(A) != 0:
			new_A = A[:A.index(max(A))]
			A = new_A
			game_play += 1
		print('ANDY' if game_play % 2 == 0 else 'BOB')


for i in range(int(input())):
	n = int(input())
	k = 0
	f = 0
	l = list(map(int, input().split()))
	if sorted(l) == l:
		f = 1
		if n % 2 == 0:
			print('ANDY')
		else:
			print('BOB')
	else:
		while l != []:
			a = max(l)
			l = l[:l.index(a)]
			k += 1
		if k % 2 == 0:
			print('ANDY')
		else:
			print('BOB')


import sys
g = int(input().strip())
for _ in range(g):
	n = int(input().strip())
	A = [int(a) for a in input().strip().split(' ')]
	if sorted(A) == A:
		print('ANDY' if len(A) % 2 == 0 else 'BOB')
	else:
		game_play = 0
		while len(A) != 0:
			new_A = A[:A.index(max(A))]
			A = new_A
			game_play += 1
		print('ANDY' if game_play % 2 == 0 else 'BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	nums = list(map(int, input().split()))
	maxi = [None] * n
	maxv = [None] * n
	maxi[0] = 0
	maxv[0] = nums[0]
	for i in range(1, n):
		if nums[i] > maxv[i - 1]:
			maxi[i] = i
			maxv[i] = nums[i]
		else:
			maxi[i] = maxi[i - 1]
			maxv[i] = maxv[i - 1]
	if len(set(maxi)) % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


q = int(input())
for _ in range(q):
	n = int(input())
	a = [int(x) for x in input().strip().split(' ')]
	if sorted(a) == a:
		if len(a) % 2 == 0:
			print('ANDY')
		else:
			print('BOB')
	else:
		numberofmove = 0
		while len(a) != 0:
			temp = a[:a.index(max(a))]
			a = temp
			numberofmove += 1
		if numberofmove % 2 == 0:
			print('ANDY')
		else:
			print('BOB')


for case in range(int(input())):
	N = int(input())
	(max_x, peaks) = (0, 0)
	for x in map(int, input().split()):
		if x > max_x:
			max_x = x
			peaks += 1
	print('BOB' if peaks % 2 else 'ANDY')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	p = list(map(int, input().strip().split()))
	k = 0
	g = 0
	for i in p:
		if k < i:
			g += 1
			k = i
	if g % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	a = list(map(int, input().split()))
	l = [a[0]]
	j = 1
	for i in range(1, n):
		if a[i] > l[j - 1]:
			l.append(a[i])
			j += 1
	if j % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys

def eprint(*argv, **kwargv):
	print(*argv, file=sys.stderr, **kwargv)
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	arr = list(map(int, input().split(' ')))
	arr = sorted(enumerate(arr), key=lambda x: -x[1])
	turns = 0
	maxindex = len(arr)
	for (i, val) in arr:
		if i > maxindex:
			continue
		maxindex = i
		turns += 1
		if i == 0:
			break
	eprint(turns)
	if turns % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys
g = int(input().strip())
for _ in range(g):
	n = int(input().strip())
	arr = [int(x) for x in input().split()]
	terms = 0
	max_so_far = 0
	for i in range(n):
		current = arr[i]
		if current > max_so_far:
			max_so_far = current
			terms += 1
	if terms % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


t = int(input())
while t > 0:
	n = int(input())
	list = [int(x) for x in input().split()]
	c = 0
	max = list[0]
	for x in list:
		if x > max:
			max = x
			c += 1
	if c % 2 == 1:
		print('ANDY')
	else:
		print('BOB')
	t -= 1


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	ar = [int(i) for i in input().strip().split(' ')]
	current_max = -1
	counter = 0
	for x in ar:
		if x > current_max:
			counter += 1
			current_max = x
	if counter % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	L = [int(x) for x in input().strip().split()]
	m = L[0]
	l = len(L)
	c = 1
	for i in range(1, l):
		if L[i] > m:
			m = L[i]
			c += 1
	if c % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	q = list(map(int, input().split(' ')))
	moves = 0
	maxval = -1
	for i in q:
		if maxval < i:
			moves = moves + 1
			maxval = i
	if moves % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	arr = list(map(int, input().strip().split()))
	max = 0
	m = 0
	for i in range(0, n):
		if arr[i] > max:
			max = arr[i]
			m += 1
	if m % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	arr = [int(x) for x in input().split()]
	count = 0
	max = arr[0]
	for i in range(1, n):
		if arr[i] > max:
			max = arr[i]
			count += 1
	if count % 2 == 0:
		print('BOB')
	else:
		print('ANDY')


num = int(input())
for i in range(num):
	input()
	A = list(map(int, input().strip().split(' ')))
	temp = 1
	M = A[0]
	for i in range(1, len(A)):
		if A[i] > M:
			temp += 1
			M = A[i]
	if temp % 2 == 1:
		print('BOB')
	else:
		print('ANDY')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	arr = list(map(int, input().strip().split()))
	count = 0
	top = None
	for num in arr:
		if not top or num > top:
			top = num
			count += 1
	if count % 2 == 1:
		print('BOB')
	else:
		print('ANDY')


import sys
(p1, p2) = ('BOB', 'ANDY')
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	l = [int(x) for x in input().split()]
	if sorted(l) == l:
		if n % 2 == 0:
			print(p2)
		else:
			print(p1)
	else:
		p = 0
		while len(l) != 0:
			p += 1
			l = l[:l.index(max(l))]
		p -= 1
		if p % 2 == 0:
			print(p1)
		else:
			print(p2)


for a0 in range(int(input().strip())):
	n = int(input().strip())
	A = list(map(int, input().split()))
	for i in range(1, n):
		A[i] = max(A[i - 1], A[i])
	print(['ANDY', 'BOB'][len(set(A)) % 2])


import sys
g = int(input().strip())
for _ in range(g):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	max_a = [a[0]]
	for i in range(1, n):
		if a[i] > max_a[-1]:
			max_a.append(a[i])
	if len(max_a) % 2 != 0:
		winner = 'BOB'
	else:
		winner = 'ANDY'
	print(winner)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = defaultdict(lambda : -1)
	for i in range(len(arr)):
		d[arr[i]] = i
	arr.sort(reverse=True)
	deletedTo = d[arr[0]]
	moves = 1
	ind = 1
	while deletedTo != 0:
		while ind < len(arr) and d[arr[ind]] > deletedTo:
			ind += 1
		if ind == len(arr):
			break
		else:
			moves += 1
			deletedTo = d[arr[ind]]
			ind += 1
	print('ANDY' if moves % 2 == 0 else 'BOB')


import sys
import bisect
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	arr = list(map(int, input().strip().split(' ')))
	max_so_far = (arr[0], 0)
	max_to_the_left = []
	for (i, elem) in enumerate(arr):
		max_so_far = max(max_so_far, (elem, i))
		max_to_the_left.append(max_so_far)
	index = n - 1
	c = 0
	while index >= 0:
		(_, i) = max_to_the_left[index]
		index = i - 1
		c += 1
	print('ANDY' if c % 2 == 0 else 'BOB')


def game(n, arr):
	coun = 1
	maxi = arr[0]
	for i in range(1, n):
		if arr[i] > maxi:
			coun += 1
			maxi = arr[i]
	return coun
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	a = game(n, arr)
	if a % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


def ans():
	for _ in range(int(input())):
		input()
		cache = 0
		vmax = 0
		for i in map(int, input().split()):
			if i > vmax:
				cache ^= 1
				vmax = i
		yield ('BOB' if cache else 'ANDY')
print('\n'.join(ans()))


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	arr = [int(i) for i in input().split(' ')]
	moves = 0
	maxsofar = 0
	for i in range(n):
		value = arr[i]
		if value > maxsofar:
			maxsofar = value
			moves += 1
	if moves % 2 == 1:
		print('BOB')
	else:
		print('ANDY')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	nums = [int(a) for a in input().strip().split(' ')]
	moves = 0
	max_index = nums.index(max(nums))
	if max_index is 0:
		print('BOB')
		continue
	curr_max = 0
	for i in range(len(nums)):
		if nums[i] > curr_max:
			curr_max = nums[i]
			moves += 1
	if moves % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys

def game(array):
	BOB = True
	bound = len(array)
	maxes = [0]
	for i in range(bound):
		if array[maxes[-1]] < array[i]:
			maxes.append(i)
	while len(maxes) > 0:
		index_of_max = maxes.pop()
		bound = index_of_max
		BOB = not BOB
	if BOB:
		print('ANDY')
	else:
		print('BOB')
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	array = list(map(int, input().split()))
	game(array)


import sys

def print_winner(A):
	game_array = [0]
	for a in A:
		if a > game_array[-1]:
			game_array.append(a)
	if len(game_array) % 2 == 0:
		print('BOB')
	else:
		print('ANDY')
	return None
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	A = [int(x) for x in input().strip().split(' ')]
	print_winner(A)


import sys
g = int(input().strip())
for _ in range(g):
	n = int(input().strip())
	A = [int(a) for a in input().strip().split(' ')]
	if sorted(A) == A:
		print('ANDY' if len(A) % 2 == 0 else 'BOB')
	else:
		game_play = 0
		while len(A) != 0:
			new_A = A[:A.index(max(A))]
			A = new_A
			game_play += 1
		print('ANDY' if game_play % 2 == 0 else 'BOB')


import sys

def Solve(a, n):
	player = ['ANDY', 'BOB']
	p = 0
	win = ''
	x = 0
	for i in range(0, n):
		y = a[i]
		if y > x:
			x = y
			p += 1
	win = player[p % 2]
	return win
g = int(input().strip())
for a0 in range(g):
	a = []
	n = int(input().strip())
	a = [int(x) for x in input().strip().split(' ')]
	print(Solve(a, n))


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	arr = map(int, input().split(' '))
	max_value = 0
	turns = 0
	for value in arr:
		if max_value < value:
			max_value = value
			turns += 1
	if turns % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	A = [int(c) for c in input().strip().split()]
	count = 0
	currentMax = -1
	for a in A:
		if a > currentMax:
			count += 1
			currentMax = a
	if count % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


for __ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mx = a[0]
	p = 1
	for i in range(1, n):
		if a[i] > mx:
			p += 1
			mx = a[i]
	if p % 2:
		print('BOB')
	else:
		print('ANDY')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	arr = list(map(int, input().split(' ')))
	c = 0
	m = 0
	for i in range(n):
		if arr[i] > m:
			m = arr[i]
			c += 1
	if c % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys

def findMaxIndex(array):
	m = 0
	index = 0
	for i in range(len(array)):
		m = array[i] if array[i] > m else m
		index = i
	return index
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	array = [int(i) for i in input().split(' ')]
	player = 1
	(maxCount, maxValue) = (0, 0)
	for i in range(len(array)):
		if array[i] > maxValue:
			maxValue = array[i]
			maxCount += 1
			player = not player
	print('ANDY' if player else 'BOB')


import sys
players = ['BOB', 'ANDY']
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	arr = [int(x) for x in input().split()]
	h = 0
	turns = 1
	for x in arr:
		if x > h:
			h = x
			turns += 1
	print(players[turns % 2])


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	arr = list(map(int, input().strip().split()))
	plays = 0
	maxn = 0
	for i in range(n):
		if maxn < arr[i]:
			maxn = arr[i]
			plays += 1
	if plays % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	A = [int(a) for a in input().split()]
	s = 1
	m = A[0]
	for i in range(1, len(A)):
		if A[i] > m:
			m = A[i]
			s += 1
	if s % 2 == 1:
		print('BOB')
	else:
		print('ANDY')


g = int(input())
for _ in range(g):
	n = int(input())
	a = [int(x) for x in input().split()]
	greatest = 0
	counter = 0
	for x in a:
		if x > greatest:
			counter += 1
			greatest = x
	print('ANDY' if counter % 2 == 0 else 'BOB')


for cases in range(int(input())):
	tamanio = int(input())
	array = [int(i) for i in input().split()]
	sentinela = array[0]
	contador = 1
	for i in range(1, tamanio):
		if sentinela < array[i]:
			contador += 1
			sentinela = array[i]
	print('ANDY' if contador % 2 == 0 else 'BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	game = input().split()
	newarray = [int(game[0])]
	for i in game:
		if int(i) > newarray[-1]:
			newarray.append(int(i))
	if len(newarray) % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys
g = int(input().strip())
gameArrays = []
for (index, line) in enumerate(sys.stdin):
	if index % 2 == 1:
		array = []
		localMax = -1
		for a in line.split():
			if int(a) > localMax:
				array.append(int(a))
				localMax = int(a)
		gameArrays.append(array[:])
for array in gameArrays:
	if len(array) % 2 == 0:
		print('ANDY')
	else:
		print('BOB')
print()


def solve():
	bob = True
	last = nums[0]
	for i in range(1, n):
		if nums[i] > last:
			last = nums[i]
			bob = not bob
	if bob:
		print('BOB')
	else:
		print('ANDY')
q = int(input())
for i in range(q):
	n = int(input())
	s = input()
	nums = list(map(lambda n: int(n), s.split(' ')))
	solve()


t = int(input())
for a0 in range(t):
	n = int(input())
	k = 0
	res = list(map(int, input().split(' ')))
	i = 0
	MAX = 0
	while i < len(res):
		c = res[i]
		if c > MAX:
			MAX = c
			k = k + 1
		i = i + 1
	if k % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	arr = [int(a) for a in input().split()]
	count = 1
	maxi = arr[0]
	for i in range(1, n):
		if arr[i] > maxi:
			count += 1
			maxi = arr[i]
	if count % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	count = 1
	arr = [int(x) for x in input().split(' ')]
	mx = arr[0]
	for i in range(1, len(arr)):
		if arr[i] > mx:
			count += 1
			mx = arr[i]
	if count % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


for _ in range(int(input())):
	(n, arr) = (int(input()), list(map(int, input().split())))
	c = 0
	m = 0
	for i in range(n):
		if arr[i] > m:
			m = arr[i]
			c += 1
	print('ANDY' if c % 2 == 0 else 'BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	array_vals = input().strip().split(' ')
	array_vals = [int(i) for i in array_vals]
	total = 1
	current = array_vals[0]
	for i in range(1, n):
		if array_vals[i] > current:
			current = array_vals[i]
			total += 1
	if total % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	a = [int(x) for x in input().split(' ')]
	turns = 0
	target = 0
	highest = 0
	for v in a:
		if v > target and v > highest:
			highest = v
			turns += 1
		target = v
	print('BOB' if turns % 2 == 1 else 'ANDY')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	nums = list(map(int, input().split()))
	moves = 0
	currentMax = -sys.maxsize
	for i in range(len(nums)):
		if currentMax < nums[i]:
			currentMax = nums[i]
			moves += 1
	if moves % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	num_maxes = 0
	max = 0
	for num in input().split():
		if int(num) > max:
			max = int(num)
			num_maxes += 1
	print('BOB' if num_maxes % 2 == 1 else 'ANDY')


def f():
	q = int(input())
	for i in range(q):
		n = int(input())
		arr = []
		for j in range(2 * n):
			row = [int(z) for z in input().split()]
			arr.append(row)
		sums = 0
		for j in range(n):
			for k in range(n):
				a1 = arr[j][k]
				a2 = arr[j][2 * n - 1 - k]
				a3 = arr[2 * n - 1 - j][k]
				a4 = arr[2 * n - 1 - j][2 * n - 1 - k]
				sums += max(a1, a2, a3, a4)
		print(sums)

def s():
	g = int(input())
	for i in range(g):
		n = int(input())
		arr = [int(j) for j in input().split()]
		times = 0
		nums = 0
		for j in arr:
			if j > nums:
				nums = j
				times += 1
		if times % 2:
			print('BOB')
		else:
			print('ANDY')
s()


import sys

def argmax(arr):
	ind = arr.index(max(arr))
	return ind
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	a = [int(c_temp) for c_temp in input().strip().split(' ')]
	moves = 0
	maxv = 0
	for i in range(n):
		c = a[i]
		if c > maxv:
			maxv = c
			moves = moves + 1
	if moves % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	arr = list(map(int, input().split(' ')))
	st = []
	ma = 0
	for i in range(0, len(arr)):
		if arr[i] > ma:
			ma = arr[i]
			st.append(i)
	if len(st) % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


import sys
numgames = int(input().strip())
for g in range(numgames):
	n = int(input().strip())
	A = list(map(int, input().split()))
	m = 0
	bobWins = False
	for ai in A:
		if ai > m:
			m = ai
			bobWins = not bobWins
	if bobWins:
		print('BOB')
	else:
		print('ANDY')


import sys

def game(a):
	moves = 0
	temp_max = 0
	for v in a:
		if v > temp_max:
			temp_max = v
			moves += 1
	print('BOB' if moves & 1 else 'ANDY')
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	game(a)


import sys
g = int(input().strip())
for a0 in range(g):
	N = int(input().strip())
	arr = list(map(int, input().split()))
	m = 0
	maxi = 0
	for i in range(N):
		v = arr[i]
		if v > maxi:
			maxi = v
			m += 1
	if m % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


def play(player, l):
	maxL = []
	for x in l:
		if len(maxL) == 0:
			maxL.append(x)
		elif x > maxL[-1]:
			maxL.append(x)
	if len(maxL) % 2 == 0:
		print('ANDY')
	else:
		print('BOB')

def main():
	g = int(input())
	for i in range(g):
		n = int(input())
		l = [int(x) for x in input().split(' ')]
		play(1, l)
main()


import sys

def winner(arr):
	score = 1
	ind = len(arr)
	while ind > 0:
		score += 1
		ind = arr.index(max(arr[:ind]))
	player = ['BOB', 'ANDY']
	return player[score % 2]

def useTrickToCalcWinner(arr):
	score = 1
	maxsofar = 0
	for val in arr:
		if val > maxsofar:
			score += 1
			maxsofar = val
	player = ['BOB', 'ANDY']
	return player[score % 2]
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	arr = [int(atemp) for atemp in input().strip().split(' ')]
	print(useTrickToCalcWinner(arr))


import sys
g = int(input().strip())
for a0 in range(g):
	n = int(input().strip())
	game = map(int, input().strip().split())
	if n == 0:
		print('ANDY')
		continue
	elif n == 1:
		print('BOB')
		continue
	maxes = []
	cur_max = -float('inf')
	for (i, num) in enumerate(game):
		if num > cur_max:
			cur_max = num
			maxes.append(i)
	if len(maxes) % 2 == 0:
		print('ANDY')
	else:
		print('BOB')


g = int(input())
for i in range(g):
	n = int(input())
	x = [int(j) for j in input().split()]
	y = list(dict(zip(x, range(n))).items())
	y.sort(reverse=True)
	players = ['BOB', 'ANDY']
	c = -1
	i = 0
	index = n
	while index != 0:
		if y[i][1] <= index:
			index = y[i][1]
			c += 1
		i += 1
	print(players[c % 2])


for case in range(int(input())):
	N = int(input())
	(max_x, peaks) = (0, 0)
	for x in map(int, input().split()):
		if x > max_x:
			max_x = x
			peaks += 1
	print('BOB' if peaks % 2 else 'ANDY')


t = int(input())
for _ in range(0, t):
	n = int(input())
	a = [int(i) for i in input().split()]
	dic = {}
	for i in range(0, n):
		dic[a[i]] = i
	index = a.index(max(a))
	cunt = 1
	for key in sorted(dic, reverse=True):
		if index > dic[key]:
			index = dic[key]
			cunt += 1
	if cunt % 2 == 0:
		print('ANDY')
	else:
		print('BOB')