Alice and Bob are playing a game on an array $a$ of $n$ positive integers. Alice and Bob make alternating moves with Alice going first.

In his/her turn, the player makes the following move:

If $a_1 = 0$, the player loses the game, otherwise:

Player chooses some $i$ with $2\le i \le n$. Then player decreases the value of $a_1$ by $1$ and swaps $a_1$ with $a_i$.

Determine the winner of the game if both players play optimally.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ $(1 \leq t \leq 2 \cdot 10^4)$  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ $(2 \leq n \leq 10^5)$  — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1,a_2 \ldots a_n$ $(1 \leq a_i \leq 10^9)$  — the elements of the array $a$.

It is guaranteed that sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, if Alice will win the game, output "Alice". Otherwise, output "Bob".

You can output each letter in any case. For example, "alIcE", "Alice", "alice" will all be considered identical.


-----Examples-----

Input
3
2
1 1
2
2 1
3
5 4 4
Output
Bob
Alice
Alice


-----Note-----

In the first testcase, in her turn, Alice can only choose $i = 2$, making the array equal $[1, 0]$. Then Bob, in his turn, will also choose $i = 2$ and make the array equal $[0, 0]$. As $a_1 = 0$, Alice loses.

In the second testcase, once again, players can only choose $i = 2$. Then the array will change as follows: $[2, 1] \to [1, 1] \to [1, 0] \to [0, 0]$, and Bob loses.

In the third testcase, we can show that Alice has a winning strategy.

Difficulty: EASY
Tags: Game theory

Starter code:

Solutions:
import sys
input = sys.stdin.readline
list_input = lambda x=int: list(map(x, input().strip().split()))
mult_input = lambda x=int: map(x, input().strip().split())
str_input = lambda : input().rstrip('/r/n')

def solve():
	n = int(input())
	a = list_input()
	if a[0] == 1:
		return 'Bob'
	if a.count(1):
		return 'Alice'
	if a[0] == 2:
		return 'Bob'
	if a[0] == min(a):
		return 'Bob'
	return 'Alice'
for _ in range(int(input())):
	x = solve()
	if x is not None:
		print(x)


for s in [*open(0)][2::2]:
	(x, *a) = map(int, s.split())
	print('ABloibc e'[x <= min(a)::2])


for s in [*open(0)][2::2]:
	(x, *a) = map(int, s.split())
	print(('Bob', 'Alice')[x > min(a)])


import sys
from bisect import bisect_left, bisect_right
from heapq import heapify, heappush, heappop
from collections import deque
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for _ in range(ii()):
	n = ii()
	arr = il()
	if min(arr) == arr[0]:
		print('Bob')
	else:
		print('Alice')


import sys
from typing import List, Tuple

def inint():
	return int(sys.stdin.readline())

def inlist():
	return list(map(int, sys.stdin.readline().split()))

def instr():
	s = sys.stdin.readline()
	return list(s[:len(s) - 1])

def invar():
	return map(int, sys.stdin.readline().split())
for i in range(inint()):
	sys.stdin.readline()
	l = inlist()
	if min(l) == l[0]:
		print('Bob')
	else:
		print('Alice')


t = int(input())
result = ''
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	result += ('Bob' if a[0] == min(a) else 'Alice') + '\n'
print(result[:-1])


import fileinput

def main():
	lines = fileinput.input()
	ntests = int(next(lines).rstrip('\n'))
	for test in range(ntests):
		n = int(next(lines).rstrip('\n'))
		a = [int(num) for num in next(lines).rstrip('\n').split(' ')]
		if a[0] <= min(a):
			print('Bob')
		else:
			print('Alice')
main()


import sys
input = sys.stdin.readline

def solution(items: list, n: int):
	min_idx = 1
	for i in range(2, n):
		if items[i] < items[min_idx]:
			min_idx = i
	return 'Alice' if items[min_idx] < items[0] else 'Bob'
t = int(input())
for _ in range(t):
	n = int(input())
	items = list(map(int, input().split()))
	print(solution(items, n))


import sys
input = sys.stdin.readline

def readList():
	return list(map(int, input().split()))

def readInt():
	return int(input())

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

def readStr():
	return input().strip()

def solve():
	n = readInt()
	arr = readList()
	v = min(arr)
	return 'Bob' if arr[0] == v else 'Alice'
for _ in range(int(input())):
	print(solve())


turns = int(input())
results = []
for _ in range(turns):
	len = input()
	a = list(map(int, input().split()))
	if a[0] == min(a):
		results.append('Bob')
	else:
		results.append('Alice')
for res in results:
	print(res)


n = int(input())
rounds = 0
out = []
for i in range(n):
	x = int(input())
	L = list(map(int, input().strip().split()))
	if min(L) == L[0]:
		out += ['Bob']
	else:
		out += ['Alice']
for i in out:
	print(i)


import sys
input = sys.stdin.readline

def solution(items: list, n: int):
	min_idx = min(range(len(items)), key=items.__getitem__)
	return 'Alice' if items[min_idx] < items[0] else 'Bob'
t = int(input())
for _ in range(t):
	n = int(input())
	items = list(map(int, input().split()))
	print(solution(items, n))


n = int(input())
a = []
for i in range(n):
	p = int(input())
	k = [int(i) for i in input().split()]
	m = 0
	for i in range(1, p):
		if k[0] > k[i]:
			a.append('Alice')
			m = 1
			break
	if m == 0:
		a.append('Bob')
for i in range(n):
	print(a[i], end='\n')


inp1 = int(input())
ans = []
chance = 'Bob'
for i in range(0, inp1):
	total_swaps = 0
	inp2 = int(input())
	inp3 = input()
	l1 = inp3.split()
	for j in range(0, len(l1)):
		l1[j] = int(l1[j])
	if min(l1) != l1[0]:
		ans.append('Alice')
	else:
		ans.append('Bob')
for k in ans:
	print(k)


num_tests = int(input())
for _ in range(num_tests):
	L = int(input())
	arr = list(map(int, input().split()))
	if min(arr) != arr[0]:
		print('Alice')
	else:
		print('Bob')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	f = False
	for i in a[1:]:
		if a[0] > i:
			f = True
	if not f:
		print('Bob')
	else:
		print('Alice')


t = int(input())
for _ in range(t):
	n = int(input())
	(*a,) = map(int, input().split())
	if min(a) != a[0]:
		print('Alice')
	else:
		print('Bob')


try:
	for _ in range(int(input())):
		n = int(input())
		l = list(map(int, input().split(' ')))
		mn = min(l)
		if l[0] == mn:
			print('Bob')
		else:
			print('Alice')
except:
	pass


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = min(l)
	if d == l[0]:
		print('Bob')
	else:
		print('Alice')


def solve(n, a):
	if a[0] > min(a):
		return 'Alice'
	else:
		return 'Bob'
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(component) for component in input().split(' ')]
	print(solve(n, a))


tesrty67 = int(input())
for tc4tr67 in range(tesrty67):
	oihgd = int(input())
	lsrytr = list(map(int, input().split()))
	deftudchg = min(lsrytr)
	if lsrytr[0] == deftudchg:
		print('Bob')
	else:
		print('Alice')


t = int(input())
while t:
	num = int(input())
	num_arr = list(map(int, input().split()))
	a = min(num_arr)
	b = num_arr.index(a)
	if b == 0:
		print('Bob')
	else:
		print('Alice')
	t -= 1


k = int(input())
for q in range(k):
	n = int(input())
	a = list(map(int, input().split()))
	aa = min(a)
	if aa == a[0]:
		print('Bob')
	else:
		print('Alice')


for i in range(int(input())):
	len = int(input())
	arr = [int(item) for item in input().split()]
	print('Bob' if arr[0] == min(arr) else 'Alice')


def solve():
	n = int(input())
	A = list(map(int, input().split()))
	if A[0] > min(A[1:]):
		print('Alice')
	else:
		print('Bob')
for _ in range(int(input())):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	nums = [int(j) for j in input().split()]
	if min(nums) == nums[0]:
		print('Bob')
	else:
		print('Alice')


t = int(input())
for i in range(t):
	n = int(input())
	w = [int(k) for k in input().split()]
	if w[0] == min(w):
		print('Bob')
	else:
		print('Alice')


t = int(input())
for i in range(t):
	n = int(input())
	num = list(map(int, input().split()))
	print('Bob' if num[0] == min(num) else 'Alice')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr1 = sorted(arr)
	if arr1[0] != arr[0]:
		print('Alice')
	else:
		print('Bob')


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	print('Alice' if min(s[1:]) < s[0] else 'Bob')


n = int(input())
for j in range(n):
	num = int(input())
	x = input()
	S = [int(n1) for n1 in x.split()]
	min_f = 10 ** 9
	min_s = min_f - 1
	for S_n in S:
		if S_n < min_f:
			min_s = min_f
			min_f = S_n
	if S[0] == min_f:
		print('Bob')
	elif S[0] == min_s:
		print('Alice')
	elif S[0] >= min_f:
		print('Alice')


for f in range(int(input())):
	n = int(input())
	listt = list(map(int, input().split()))
	if listt.index(min(listt)) != 0:
		print('Alice')
	else:
		print('Bob')


def readInt():
	return int(input())

def readIntList():
	return list(map(int, input().split()))

def readStringList():
	return list(input())

def readStringListWithSpace():
	return list(input().split())

def readString():
	return input()
import math
TC = readInt()
for tc in range(TC):
	n = readInt()
	a = readIntList()
	bob = a[0]
	alice = min(a[1:])
	if bob <= alice:
		print('Bob')
	else:
		print('Alice')


test = int(input())
for _ in range(test):
	number = int(input())
	array = list(map(int, input().split()))
	temp = min(array)
	if array[0] == temp:
		print('Bob')
	else:
		print('Alice')


def N():
	return int(input())

def A():
	return [int(x) for x in input().split()]

def S():
	return input()
for _ in range(N()):
	n = N()
	if 'codeforces' == 28226329:
		print('Tanmay')
	a = A()
	if min(a) != a[0]:
		print('Alice')
		continue
	print('Bob')


n = int(input())
for i in range(n):
	b = int(input())
	a = list(map(int, input().split()))
	m = min(a)
	if a[0] == m:
		print('Bob')
	else:
		print('Alice')


n = int(input())
for i in range(n):
	m = int(input())
	l = [int(x) for x in input().split()]
	if l[0] == min(l):
		print('Bob')
	else:
		print('Alice')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(sep=' ')))
	s = min(a)
	if s == a[0]:
		print('Bob')
	else:
		print('Alice')


case = int(input())
for case in range(case):
	n = int(input())
	mas = list(map(int, input().split()))
	if mas[0] == min(mas):
		print('Bob')
	else:
		print('Alice')


t = int(input())
while t:
	t -= 1
	n = int(input())
	sum = 0
	A = [*map(int, input().split())]
	print(['Alice', 'Bob'][A[0] <= min(A[1:])])


for i in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	a = s[0]
	l = min(s[1:])
	if a > l:
		print('Alice')
	else:
		print('Bob')


def main():
	for t in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		print('Alice' if a[0] != min(a) else 'Bob')
main()


cnt = 0
for _ in range(int(input())):
	l = input()
	a = list(map(int, input().split()))
	if a.index(min(a)) != 0:
		print('Alice')
	else:
		print('Bob')


for _ in range(int(input())):
	l = int(input())
	nums = list(map(int, input().split()))
	min_ = min(nums)
	if nums[0] == min_:
		print('Bob')
	else:
		print('Alice')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a1 = a[0]
	a2 = min(a[1:])
	if a1 > a2:
		print('Alice')
	else:
		print('Bob')


a = int(input())
while a:
	input()
	x = list(map(int, input().split()))
	print('Bob' if min(x) == x[0] else 'Alice')
	a -= 1


for _ in range(int(input())):
	input()
	lista = list(map(int, input().split()))
	print('Alice' if lista[0] > min(lista) else 'Bob')


def solve():
	n = int(input())
	nums = list(map(int, input().split()))
	if min(nums) == nums[0]:
		print('Bob')
	else:
		print('Alice')
t = int(input())
for i in range(t):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	minimum = min(arr)
	if arr[0] > minimum:
		print('Alice')
	else:
		print('Bob')


T = int(input())
for _ in range(T):
	n = int(input())
	a = tuple(map(int, input().split()))
	if a[0] > min(a[1:]):
		print('Alice')
	else:
		print('Bob')


for _ in range(int(input())):
	n = int(input())
	l = [*map(int, input().split())]
	print(['Alice', 'Bob'][min(l) == l[0]])


def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		m = min(arr)
		if arr[0] == m:
			print('Bob')
		else:
			print('Alice')
main()