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 ≤ N ≤ 2*10^5) - the length of the array A.

The second line contains N integers A_1, A_2,...,A_N (0 ≤ A_i ≤ 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
3
5 6 5
 2
5 12

Bob
 Alice

"""
E. Array Game
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output

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≤N≤2∗105) - the length of the array A.

The second line contains N integers A1, A2,...,AN (0≤Ai≤109)

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".
"""

from collections import deque


def array_game(array):
    turn = True
    array = deque(array)
    sequence = []
    while True:
        if not sequence:
            get = array.popleft if array[0] > array[-1] else array.pop
            sequence.append(get())
            turn = not turn  # move successful, the other's turn
            continue
        if array:
            if array[0] <= sequence[-1] and array[-1] <= sequence[-1]:
                turn = not turn  # player can't move, switch turns to print the winner
                break
            elif array[0] > array[-1] and (array[0] > sequence[-1]):
                sequence.append(array.popleft())
                turn = not turn  # move successful, the other's turn
                continue
            elif array[-1] > array[0] and (array[-1] > sequence[-1]):
                sequence.append(array.pop())
                turn = not turn  # move successful, the other's turn
                continue
        else:
            turn = not turn  # player can't move, switch turns to print the winner
            break
    text = "Alice" if turn else "Bob"
    print(text)


if __name__ == '__main__':
    N = input()
    integers = input().split(" ")
    integers = [int(el) for el in integers]
    array_game(integers)
    # array_game([5])
    # array_game([5, 4, 5])
    # array_game([5, 8, 2, 1, 10, 9])
