Alice and Bob are playing a game. They are given an array $A$ of length $N$. The array consists of integers. They are building a sequence together. In the beginning, the sequence is empty. In one turn a player can remove a number from the left or right side of the array and append it to the sequence. The rule is that the sequence they are building must be strictly increasing. The winner is the player that makes the last move. Alice is playing first. Given the starting array, under the assumption that they both play optimally, who wins the game?


-----Input-----

The first line contains one integer $N$ ($1 \leq N \leq 2*10^5$) - the length of the array $A$.

The second line contains $N$ integers $A_1$, $A_2$,...,$A_N$ ($0 \leq A_i \leq 10^9$)


-----Output-----

The first and only line of output consists of one string, the name of the winner. If Alice won, print "Alice", otherwise, print "Bob".


-----Examples-----

Input
1
5
Output
Alice
Input
3
5 4 5
Output
Alice
Input
6
5 8 2 1 10 9
Output
Bob


-----Note-----

None

Difficulty: HARD
Tags: Amortized analysis

Game theory

Greedy algorithms
Skill types: Amortized analysis

Greedy algorithms

Starter code:

Solutions:
q = int(input())
a = list(map(int, input().split()))
(l, r) = (0, q - 1)
while l + 1 < q and a[l] < a[l + 1]:
	l += 1
while r >= 0 and a[r] < a[r - 1]:
	r -= 1
l = l + 1
r = q - r
if l % 2 or r % 2:
	print('Alice')
else:
	print('Bob')


from sys import stdin, stdout
from collections import defaultdict
input = stdin.readline
from random import randint
import math
import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
a = list(map(int, input().split()))
Left = 0
Right = n - 1
while Left != n - 1 and a[Left + 1] > a[Left]:
	Left += 1
while Right != 0 and a[Right - 1] > a[Right]:
	Right -= 1
Left += 1
Right = n - Right
if Left % 2 or Right % 2:
	print('Alice')
else:
	print('Bob')


length = int(input())
arr = input().split(' ')
arr = list(map(int, arr))
go = True
currentHigh = -1
player = 1
leftMax = 1
rightMax = 1
for i in range(length - 1):
	if arr[i] < arr[i + 1]:
		leftMax += 1
	else:
		break
for i in range(length - 1):
	if arr[-(i + 1)] < arr[-(i + 2)]:
		rightMax += 1
	else:
		break

def won(player):
	global go
	if player % 2 != 0:
		print('Alice')
	else:
		print('Bob')
	go = False

def pick(d):
	global currentHigh, player
	if d == 'L':
		if currentHigh >= arr[0]:
			won(player + 1)
		currentHigh = arr.pop(0)
	else:
		if currentHigh >= arr[-1]:
			won(player + 1)
		currentHigh = arr.pop(-1)
	player += 1
while go:
	left = arr[0]
	right = arr[-1]
	if left == right:
		if leftMax % 2 != 0 or rightMax % 2 != 0:
			won(player)
		else:
			won(player + 1)
	if left > right:
		if leftMax % 2 != 0:
			won(player)
		else:
			rightMax -= 1
			pick('R')
	if right > left:
		if rightMax % 2 != 0:
			won(player)
		else:
			leftMax -= 1
			pick('L')


n = int(input())
arr = list(map(int, input().split()))
prenum = 1
while prenum < n and arr[prenum] > arr[prenum - 1]:
	prenum += 1
surnum = n - 2
while surnum >= 0 and arr[surnum] > arr[surnum + 1]:
	surnum -= 1
front = 0
rear = n - 1
result = 0
while front <= prenum and rear >= surnum:
	if front == prenum or rear == surnum:
		result += prenum - front + rear - surnum - 1
		break
	if arr[front] < arr[rear]:
		if rear - surnum & 1:
			break
		front += 1
		result += 1
	elif arr[front] > arr[rear]:
		if prenum - front & 1:
			break
		rear -= 1
		result += 1
	else:
		if prenum - front & 1 or rear - surnum & 1:
			break
		result += 1
		break
if result & 1:
	print('Bob')
else:
	print('Alice')


length = int(input())
arr = input().split(' ')
arr = list(map(int, arr))
leftMax = 1
rightMax = 1
for i in range(length - 1):
	if arr[i] < arr[i + 1]:
		leftMax += 1
	else:
		break
for i in range(length - 1):
	if arr[-(i + 1)] < arr[-(i + 2)]:
		rightMax += 1
	else:
		break
if leftMax % 2 != 0 or rightMax % 2 != 0 or length == 1:
	print('Alice')
else:
	print('Bob')


n = int(input())
num = [int(i) for i in input().split()]
(l, r) = (0, n - 1)
while l + 1 < n and num[l] < num[l + 1]:
	l += 1
while r >= 0 and num[r] < num[r - 1]:
	r -= 1
l = l + 1
r = n - r
if l % 2 or r % 2:
	print('Alice')
else:
	print('Bob')


n = int(input())
vetor = list(map(lambda x: int(x), input().split(' ')))
right = True
left = True
for i in range(0, n - 1):
	if vetor[i + 1] <= vetor[i]:
		break
	left = not left
for j in range(n - 1, -1, -1):
	if vetor[j - 1] <= vetor[j]:
		break
	right = not right
if right or left:
	print('Alice')
else:
	print('Bob')


n = int(input())
lists = list(map(int, input().split()))
(left, right) = (0, n - 1)
while left + 1 < n and lists[left] < lists[left + 1]:
	left += 1
while right >= 1 and lists[right] < lists[right - 1]:
	right -= 1
left += 1
right = n - right
if left & 1 or right & 1:
	print('Alice')
else:
	print('Bob')


from sys import stdin
eg = False
inp = []
it0 = 0
it1 = 0
new = []
it = 0
max1 = -1
max2 = -1
va = 0
for line in stdin:
	if va == 1:
		inp = [x for x in line.strip().split()]
	va += 1
l = len(inp)

def only_one_end(it, lr):
	global inp
	global l
	if lr:
		n1 = int(inp[l - it - 1])
		n2 = int(inp[l - it - 2])
		while n2 > n1:
			it += 1
			n1 = n2
			n2 = int(inp[l - it - 2])
	else:
		n1 = int(inp[0 + it])
		n2 = int(inp[0 + it + 1])
		while n2 > n1:
			it += 1
			n1 = n2
			n2 = int(inp[0 + it + 1])
	it += 1
	return it
la = False
for i in range(l):
	n1 = int(inp[it0])
	n2 = int(inp[l - it1 - 1])
	if n1 > n2:
		la = True
		new.append(1)
		it1 += 1
		if n2 >= int(inp[l - it1 - 1]):
			it0 = only_one_end(it0, False)
			break
	elif n1 < n2:
		la = False
		new.append(0)
		it0 += 1
		if n1 >= int(inp[0 + it0]):
			it1 = only_one_end(it1, True)
			break
	elif it0 != l - it1 - 1:
		eg = True
		egPo = [it0, it1]
		it1 = only_one_end(it1, True)
		it0 = only_one_end(it0, False)
		break
	else:
		if la:
			it0 += 1
		else:
			it1 += 1
		break
it3 = 0
res = False
con = True
for e in new:
	if e == 1 and it0 % 2 == 1 or (e == 0 and it1 % 2 == 1):
		con = False
		if res:
			print('Bob')
		else:
			print('Alice')
		break
	elif e == 0:
		it0 -= 1
	else:
		it1 -= 1
	res = not res
if con:
	if it0 + it1 != 0 and (it0 % 2 == 0 and it1 % 2 == 0):
		res = not res
	if res:
		print('Bob')
	else:
		print('Alice')


n = int(input())
a = list(map(int, input().split()))
(len, r) = (0, n - 1)
while len + 1 < n and a[len] < a[len + 1]:
	len += 1
while r >= 0 and a[r] < a[r - 1]:
	r -= 1
len = len + 1
r = n - r
if len % 2 or r % 2:
	print('Alice')
else:
	print('Bob')


arraySize = int(input())
(left, right) = (0, arraySize - 1)
array = list(map(int, input().split()))
while left + 1 < arraySize and array[left] < array[left + 1]:
	left += 1
while right > 0 and array[right] < array[right - 1]:
	right -= 1
left += 1
right = arraySize - right
if left % 2 or right % 2:
	print('Alice')
else:
	print('Bob')


n = int(input())
x = list(map(int, input().split()))
(l, r) = (0, n - 1)
while l + 1 < n and x[l] < x[l + 1]:
	l += 1
while r >= 0 and x[r] < x[r - 1]:
	r -= 1
l = l + 1
r = n - r
if l % 2 or r % 2:
	print('Alice')
else:
	print('Bob')


from __future__ import division, print_function
import math
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
	return int(input())

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

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

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
n = inp()
l = inlt()
array = 0
chnce = {'Alice': 'Bob', 'Bob': 'Alice'}
strt = 'Alice'
cntl = 1
cntr = 1
for i in range(1, n):
	if l[i] > l[i - 1]:
		cntl += 1
	else:
		break
for i in range(n - 2, -1, -1):
	if l[i] > l[i + 1]:
		cntr += 1
	else:
		break
if cntl % 2 or cntr % 2:
	print(strt)
else:
	print(chnce[strt])


from collections import deque

def array_game(n, array):
	left = 0
	right = n - 1
	while left < n - 1 and array[left] < array[left + 1]:
		left += 1
	while right >= 0 and array[right] < array[right - 1]:
		right -= 1
	if left % 2 == 0 or (n - right) % 2 == 1:
		print('Alice')
	else:
		print('Bob')
N = int(input())
integers = input().split(' ')
integers = [int(el) for el in integers]
array_game(N, integers)


arrayLen = int(input())
nIntegers = list(map(int, input().split()))
left = 0
right = arrayLen - 1
while left + 1 < arrayLen and nIntegers[left] < nIntegers[left + 1]:
	left += 1
while right >= 0 and nIntegers[right] < nIntegers[right - 1]:
	right -= 1
left = left + 1
right = arrayLen - right
if left % 2 or right % 2:
	print('Alice')
else:
	print('Bob')


n = int(input())
a = list(map(int, input().split()))
Left = 0
Right = n - 1
while Left != n - 1 and a[Left + 1] > a[Left]:
	Left += 1
while Right != 0 and a[Right - 1] > a[Right]:
	Right -= 1
if (Left + 1) % 2 or (n - Right) % 2:
	print('Alice')
else:
	print('Bob')