We define the *goodness* of any array B of length M as: \sum_{i = 1}^{M - 1} |B_{i + 1} - B_{i}| (Here |X| denotes the absolute value of X). In particular, *goodness* of any array of length 1 is 0.

Alice and Bob have an array A containing N distinct elements and they play a game with it.  
Alice starts the game after which both the players make moves alternatively. In one move:
A player can delete any subarray from A such that the *goodness* of A does not change. 
 
Formally, the player chooses indices L and R such that 1 ≤ L ≤ R ≤ \mathrm{length}(A) and removes the subarray [A_{L}, A_{L + 1}, \ldots, A_{R}] from A such that the *goodness* of A does not change.

For e.g. A = [3, 1, 2, 4], a player can select L = 3, R = 3, then the resulting array will be [3, 1, 4]. Initially, the *goodness* was |1-3| + |2-1| + |4-2| = 5. After the move, the *goodness* is |1-3| + |4-1| = 5. Here we can observe that the goodness does not change.

The player who is not able to make a move loses. If both the players play optimally, determine who out of Alice and Bob will win the game.

------ Input Format ------ 

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — the size of the array A.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

------ Output Format ------ 

For each test case, output the winner of the game if both players play optimally.

You may print each character of Alice and Bob in uppercase or lowercase (for example, aLiCe, ALIce, alice will be considered identical).

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$2 ≤N ≤10^{5}$
$1 ≤A_{i} ≤10^{9}$
- All $A_{i}$ are distinct.
- Sum of $N$ over all test cases does not exceed $10^{6}$.

----- Sample Input 1 ------ 
2
3
1 3 2
4
1 2 3 4

----- Sample Output 1 ------ 
Bob
Alice

----- explanation 1 ------ 
Test case 1: Alice can not make any moves such that the goodness of the array does not change. Therefore Bob wins.

Test case 2: Alice can choose $L = 2, R = 3$ and remove the subarray $[A_{2}, A_{3}]$. The resulting array is $[1, 4]$.
- *Goodness* of the array before the operation $ = |2-1|+|3-2|+|4-3| = 3$.
- *Goodness* of the array after the operation $ = |4-1| = 3$.

Thus, the array has the same goodness as before. Now Bob can not make any move. Therefore Alice wins.

Difficulty: VERY_HARD
Tags: Game theory

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	total = []
	x = 0
	cost = 0
	for i in range(1, n - 1):
		if (a[i] - a[i - 1]) * (a[i] - a[i + 1]) > 0:
			total.append(cost)
			cost = 0
		else:
			cost += 1
	total += [cost]
	for i in total:
		x ^= i
	print(['Bob', 'Alice'][x != 0])


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	(xor, elcnt, lencntpos, lencntneg, posneg) = (0, 0, 0, 0, -1)
	arrszs = []
	for i in range(n - 1):
		if s[i + 1] > s[i]:
			lencntpos += 1
			if lencntneg >= 2:
				elcnt += 1
				arrszs.append(lencntneg - 1)
			lencntneg = 0
			posneg = 1
		elif s[i + 1] < s[i]:
			lencntneg += 1
			if lencntpos >= 2:
				elcnt += 1
				arrszs.append(lencntpos - 1)
			lencntpos = 0
			posneg = 0
		elif s[i + 1] == s[i]:
			if posneg == 1:
				lencntpos += 1
			else:
				lencntneg += 1
	if lencntpos >= 2 or lencntneg >= 2:
		elcnt += 1
		arrszs.append(max(lencntneg, lencntpos) - 1)
	for i in range(len(arrszs)):
		xor = xor ^ arrszs[i]
	if xor == 0:
		print('Bob')
	else:
		print('Alice')


def find(arr, n):
	i = 0
	flag = 1
	new = []
	while i < n - 1:
		if arr[i] > arr[i + 1]:
			j = i + 1
			while j < n - 1 and arr[j] > arr[j + 1]:
				j += 1
			new.append(j - i + 1)
			i = j
		else:
			j = i + 1
			while j < n - 1 and arr[j] < arr[j + 1]:
				j += 1
			new.append(j - i + 1)
			i = j
	flag = 0
	for i in new:
		flag ^= i - 2
	return flag
n = int(input())
for i in range(n):
	l = int(input())
	arr = list(map(int, input().split()))
	ans = find(arr, l)
	if ans == 0:
		print('Bob')
	else:
		print('Alice')


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	xor = 0
	chances = 0
	if N <= 2:
		print('Bob')
		continue
	heaps = []
	prev = 0
	for i in range(2, N):
		if A[i] > A[i - 1] and A[i - 1] > A[i - 2]:
			chances += 1
		elif A[i] < A[i - 1] and A[i - 1] < A[i - 2]:
			chances += 1
		else:
			heaps.append(chances)
			chances = 0
	if chances > 0:
		heaps.append(chances)
	for i in range(len(heaps)):
		xor = xor ^ heaps[i]
	if xor == 0:
		print('Bob')
	else:
		print('Alice')


t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	i = 0
	ans = 0
	while i < n - 1:
		x = 0
		if l[i] < l[i + 1]:
			while i < n - 1 and l[i] < l[i + 1]:
				i += 1
				x += 1
		elif l[i] > l[i + 1]:
			while i < n - 1 and l[i] > l[i + 1]:
				i += 1
				x += 1
		ans ^= x - 1
	if ans == 0:
		print('Bob')
	else:
		print('Alice')


t = int(input())
for t0 in range(t):
	n = int(input())
	numbers = list(map(int, input().split()))
	red_nodes = set()
	red_nodes.add(0)
	red_nodes.add(n - 1)
	for i in range(1, n - 1):
		if numbers[i - 1] > numbers[i] and numbers[i] < numbers[i + 1] or (numbers[i - 1] < numbers[i] and numbers[i] > numbers[i + 1]):
			red_nodes.add(i)
	counter = 0
	xor_nums = []
	for i in range(0, n):
		if red_nodes.__contains__(i):
			if counter != 0:
				xor_nums.append(counter)
			counter = 0
		else:
			counter += 1
	res = 0
	for xor_num in xor_nums:
		res = res ^ xor_num
	if res == 0:
		print('Bob')
	else:
		print('Alice')


def xorSum(arr):
	s = 0
	for val in arr:
		s ^= val
	return s

def getSeq(arr):
	seqs = []
	i = 1
	currLen = 1
	par = 0
	while i < len(arr) and arr[i] == arr[i - 1]:
		i += 1
		currLen += 1
	if i >= len(arr):
		seqs.append(currLen)
		return seqs
	while i < len(arr):
		if arr[i] > arr[i - 1]:
			par = 1
		else:
			par = -1
		if par == 1:
			while i < len(arr) and arr[i] >= arr[i - 1]:
				i += 1
				currLen += 1
			if i >= len(arr):
				seqs.append(currLen)
				return seqs
			par = -1
			seqs.append(currLen)
			currLen = 1
		else:
			while i < len(arr) and arr[i] <= arr[i - 1]:
				i += 1
				currLen += 1
			if i >= len(arr):
				seqs.append(currLen)
				return seqs
			par = 1
			seqs.append(currLen)
			currLen = 1
	return seqs
for _ in range(int(input())):
	input()
	arr = [int(i) for i in input().split()]
	if len(arr) == 1:
		print('Alice')
		continue
	seq = [i - 2 for i in getSeq(arr) if i - 2 > 0]
	if xorSum(seq) != 0:
		print('Alice')
	else:
		print('Bob')


import sys, math, heapq, bisect
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)
ints = lambda : list(map(int, input().split()))

def gprint(t, ans=''):
	print(f'Case #{t + 1}:', ans)
p = 10 ** 9 + 7
inf = 10 ** 20 + 7

def find(A, n):
	res = 0
	for i in range(n):
		res ^= A[i]
	if res == 0:
		return 'Bob'
	else:
		return 'Alice'
for t in range(int(input())):
	n = int(input())
	a = ints()
	d = 0
	if a[1] < a[0]:
		d = 1
	c = 1
	b = []
	for i in range(1, n - 1):
		if a[i] < a[i + 1]:
			if d == 0:
				c += 1
			else:
				if c > 1:
					b.append(c - 1)
				c = 1
				d = 0
		elif d == 1:
			c += 1
		else:
			if c > 1:
				b.append(c - 1)
			c = 1
			d = 1
	if c > 1:
		b.append(c - 1)
	print(find(b, len(b)))


testcase = int(input())
for _ in range(testcase):
	n = int(input())
	arr = [int(num) for num in input().split()]
	lengths = []
	current_first_ind = 0
	increasing = arr[0] < arr[1]
	for (ind, num) in enumerate(arr[2:]):
		if increasing and num < arr[ind + 1]:
			lengths.append(ind - current_first_ind)
			current_first_ind = ind + 1
			increasing = False
		elif not increasing and num > arr[ind + 1]:
			lengths.append(ind - current_first_ind)
			current_first_ind = ind + 1
			increasing = True
	lengths.append(n - current_first_ind - 2)
	ans = 0
	for num in lengths:
		ans = ans ^ num
	print('Alice' if ans != 0 else 'Bob')