#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse4")
#pragma GCC optimize("unroll-loops")
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char* x) { cerr << '\"' << x << '\"'; }
void __print(const string& x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V>& x) {
  cerr << '{';
  __print(x.first);
  cerr << ", ";
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T& x) {
  int first = 0;
  cerr << '{';
  for (auto& i : x) cerr << (first++ ? ", " : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
long long mAdd(long long a, long long b, long long p) {
  if (a + b >= p)
    return a + b - p;
  else
    return a + b;
}
long long mSub(long long a, long long b, long long p) {
  if (a < b)
    return a + p - b;
  else
    return a - b;
}
void solve() {}
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  cin.exceptions(cin.failbit);
  int n;
  cin >> n;
  vector<int> v(n);
  int maxi = 0;
  int p = 0;
  for (int i = 0; i < n; i++) {
    cin >> v[i];
    if (maxi < v[i]) {
      maxi = v[i];
      p = i;
    }
  }
  if (p == 0 || n == 1) {
    cout << "Alice";
    return 0;
  }
  int i1 = 0;
  int i2 = n - 1;
  int kk = 0;
  while (i1 < n - 1 && v[i1] < v[i1 + 1]) {
    i1++;
  }
  while (i2 - 1 >= 0 && v[i2 - 1] > v[i2]) {
    i2--;
    kk++;
  }
  if (i1 == 0 || kk == 0) {
    cout << "Alice";
    return 0;
  }
  if ((kk - 1) % 2 == 0 && (i1 - 1) % 2 == 0) {
    cout << "Bob\n";
    return 0;
  } else {
    cout << "Alice";
  }
}

### Prompt

Construct a cpp code solution to the problem outlined:

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;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse4")
#pragma GCC optimize("unroll-loops")
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char* x) { cerr << '\"' << x << '\"'; }
void __print(const string& x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V>& x) {
  cerr << '{';
  __print(x.first);
  cerr << ", ";
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T& x) {
  int first = 0;
  cerr << '{';
  for (auto& i : x) cerr << (first++ ? ", " : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
long long mAdd(long long a, long long b, long long p) {
  if (a + b >= p)
    return a + b - p;
  else
    return a + b;
}
long long mSub(long long a, long long b, long long p) {
  if (a < b)
    return a + p - b;
  else
    return a - b;
}
void solve() {}
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  cin.exceptions(cin.failbit);
  int n;
  cin >> n;
  vector<int> v(n);
  int maxi = 0;
  int p = 0;
  for (int i = 0; i < n; i++) {
    cin >> v[i];
    if (maxi < v[i]) {
      maxi = v[i];
      p = i;
    }
  }
  if (p == 0 || n == 1) {
    cout << "Alice";
    return 0;
  }
  int i1 = 0;
  int i2 = n - 1;
  int kk = 0;
  while (i1 < n - 1 && v[i1] < v[i1 + 1]) {
    i1++;
  }
  while (i2 - 1 >= 0 && v[i2 - 1] > v[i2]) {
    i2--;
    kk++;
  }
  if (i1 == 0 || kk == 0) {
    cout << "Alice";
    return 0;
  }
  if ((kk - 1) % 2 == 0 && (i1 - 1) % 2 == 0) {
    cout << "Bob\n";
    return 0;
  } else {
    cout << "Alice";
  }
}

```