#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using ull = unsigned long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using vs = vector<string>;
using vvs = vector<vs>;
using vc = vector<char>;
using vvc = vector<vc>;
using ii = pair<int, int>;
using vii = vector<ii>;
using vvii = vector<vii>;
using dd = pair<double, double>;
using vdd = vector<dd>;
using vvdd = vector<vdd>;
using Mii = map<int, int>;
using vMii = vector<Mii>;
using Si = set<int>;
using vSi = vector<Si>;
using vvSi = vector<vSi>;
vi a;
bool rec(int i, int j, int left, int right) {
  if (right == 0) {
    return left & 1;
  }
  if (left == 0) return right & 1;
  if (a[i] == a[j]) {
    return (left & 1) or (right & 1);
  }
  if (a[i] > a[j]) {
    if (left & 1) return true;
    return not rec(i, j - 1, left, right - 1);
  }
  if (right & 1) return true;
  return not rec(i + 1, j, left - 1, right);
}
int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  int n;
  while (cin >> n) {
    a = vi(n);
    for (int& x : a) cin >> x;
    int left = 1;
    for (int i = 1; i < n; ++i) {
      if (a[i] > a[i - 1])
        left++;
      else
        break;
    }
    int right = 1;
    for (int i = n - 2; i >= 0; --i) {
      if (a[i] > a[i + 1])
        right++;
      else
        break;
    }
    bool guanya = rec(0, n - 1, left, right);
    cout << (guanya ? "Alice" : "Bob") << '\n';
  }
}

### Prompt

Your task is to create a Cpp solution to the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using ull = unsigned long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using vs = vector<string>;
using vvs = vector<vs>;
using vc = vector<char>;
using vvc = vector<vc>;
using ii = pair<int, int>;
using vii = vector<ii>;
using vvii = vector<vii>;
using dd = pair<double, double>;
using vdd = vector<dd>;
using vvdd = vector<vdd>;
using Mii = map<int, int>;
using vMii = vector<Mii>;
using Si = set<int>;
using vSi = vector<Si>;
using vvSi = vector<vSi>;
vi a;
bool rec(int i, int j, int left, int right) {
  if (right == 0) {
    return left & 1;
  }
  if (left == 0) return right & 1;
  if (a[i] == a[j]) {
    return (left & 1) or (right & 1);
  }
  if (a[i] > a[j]) {
    if (left & 1) return true;
    return not rec(i, j - 1, left, right - 1);
  }
  if (right & 1) return true;
  return not rec(i + 1, j, left - 1, right);
}
int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  int n;
  while (cin >> n) {
    a = vi(n);
    for (int& x : a) cin >> x;
    int left = 1;
    for (int i = 1; i < n; ++i) {
      if (a[i] > a[i - 1])
        left++;
      else
        break;
    }
    int right = 1;
    for (int i = n - 2; i >= 0; --i) {
      if (a[i] > a[i + 1])
        right++;
      else
        break;
    }
    bool guanya = rec(0, n - 1, left, right);
    cout << (guanya ? "Alice" : "Bob") << '\n';
  }
}

```