#include <bits/stdc++.h>
using namespace std;
struct Scanner {
  bool hasNext = 1;
  bool hasRead = 1;
  int nextInt() {
    hasRead = 0;
    int res = 0;
    char flag = 1, ch = getchar();
    while (ch != EOF && !isdigit(ch)) {
      hasRead = 1;
      flag = (ch == '-') ? -flag : flag;
      ch = getchar();
    }
    while (ch != EOF && isdigit(ch)) {
      hasRead = 1;
      res = res * 10 + (ch - '0');
      ch = getchar();
    }
    if (ch == EOF) hasNext = 0;
    return res * flag;
  }
  long long nextLL() {
    hasRead = 0;
    long long res = 0;
    char flag = 1, ch = getchar();
    while (ch != EOF && !isdigit(ch)) {
      hasRead = 1;
      flag = (ch == '-') ? -flag : flag;
      ch = getchar();
    }
    while (ch != EOF && isdigit(ch)) {
      hasRead = 1;
      res = res * 10 + (ch - '0');
      ch = getchar();
    }
    if (ch == EOF) hasNext = 0;
    return res * flag;
  }
  char nextChar() {
    hasRead = 0;
    char ch = getchar();
    while (ch != EOF && isspace(ch)) {
      hasRead = 1;
      ch = getchar();
    }
    if (ch == EOF) hasNext = 0;
    return ch;
  }
  int nextString(char *str) {
    hasRead = 0;
    int len = 0;
    char ch = getchar();
    while (ch != EOF && isspace(ch)) {
      hasRead = 1;
      ch = getchar();
    }
    while (ch != EOF && !isspace(ch)) {
      hasRead = 1;
      str[++len] = ch;
      ch = getchar();
    }
    str[len + 1] = 0;
    if (ch == EOF) hasNext = 0;
    return len;
  }
} sc;
long long rd() {
  long long x = sc.nextLL();
  return x;
}
void rd(int &x) { x = sc.nextInt(); }
void rd(long long &x) { x = sc.nextLL(); }
void rd(char &x) { x = sc.nextChar(); }
void rd(char *x) { sc.nextString(x); }
template <typename T1, typename T2>
void rd(pair<T1, T2> &x) {
  rd(x.first);
  rd(x.second);
}
template <typename T>
void rd(T *x, int n) {
  for (int i = 1; i <= n; ++i) rd(x[i]);
}
void printInt(int x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x >= 10) printInt(x / 10);
  putchar('0' + x % 10);
}
void printLL(long long x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x >= 10) printLL(x / 10);
  putchar('0' + x % 10);
}
void pr(int x, char ch = '\n') {
  printInt(x);
  putchar(ch);
}
void pr(long long x, char ch = '\n') {
  printLL(x);
  putchar(ch);
}
template <typename T1, typename T2>
void pr(pair<T1, T2> x, char ch = '\n') {
  pr(x.first, ' ');
  pr(x.second, ch);
}
template <typename T>
void pr(T *x, int n) {
  for (int i = 1; i <= n; ++i) pr(x[i], " \n"[i == n]);
}
template <typename T>
void pr(vector<T> &x) {
  int n = x.size();
  for (int i = 1; i <= n; ++i) pr(x[i - 1], " \n"[i == n]);
}
template <typename T>
void cmin(T &x, T y) {
  if (y < x) x = y;
}
template <typename T>
void cmax(T &x, T y) {
  if (y > x) x = y;
}
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double PI = acos(-1.0);
const double EPS = 1e-9;
const int MOD = 1000000007;
int n;
int a[200005];
vector<int> S;
vector<int> val;
void show() {
  puts("---");
  int siz = S.size();
  for (int i = siz - 1; i >= 0; --i) printf("%d ", S[i]);
  printf("\n");
  for (int i = siz - 1; i >= 0; --i) printf("%d ", val[i]);
  printf("\n");
}
struct Solver {
  void InitOnce() {}
  void Read() {
    rd(n);
    rd(a, n);
  }
  void Solve() {
    if (is_sorted(a + 1, a + 1 + n)) {
      puts("0");
      return;
    }
    int ans = 0;
    while (!is_sorted(a + 1, a + 1 + n)) {
      S.clear();
      val.clear();
      for (int i = n; i >= 1; --i) {
        int curval = 0;
        while (!S.empty() && a[i] > S.back()) {
          if (curval >= val.back())
            ++curval;
          else
            curval = val.back();
          S.pop_back();
          val.pop_back();
          cmax(ans, curval);
        }
        S.push_back(a[i]);
        val.push_back(curval);
      }
      n = S.size();
      for (int i = 1; i <= n; ++i) a[n + 1 - i] = S[i - 1];
    }
    pr(ans);
  }
} solver;
int main() {
  solver.InitOnce();
  int t = 1;
  t = INF;
  while (t--) {
    solver.Read();
    if (!sc.hasRead) break;
    solver.Solve();
    if (!sc.hasNext) break;
  }
  return 0;
}

### Prompt

Generate a Cpp solution to the following problem:

There are n psychos standing in a line. Each psycho is assigned a unique integer from 1 to n. At each step every psycho who has an id greater than the psycho to his right (if exists) kills his right neighbor in the line. Note that a psycho might kill and get killed at the same step. 

You're given the initial arrangement of the psychos in the line. Calculate how many steps are needed to the moment of time such, that nobody kills his neighbor after that moment. Look notes to understand the statement more precise.

Input

The first line of input contains integer n denoting the number of psychos, (1 ≤ n ≤ 105). In the second line there will be a list of n space separated distinct integers each in range 1 to n, inclusive — ids of the psychos in the line from left to right.

Output

Print the number of steps, so that the line remains the same afterward.

Examples

Input

10
10 9 7 8 6 5 3 4 2 1


Output

2


Input

6
1 2 3 4 5 6


Output

0

Note

In the first sample line of the psychos transforms as follows: [10 9 7 8 6 5 3 4 2 1]  →  [10 8 4] →  [10]. So, there are two steps.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
struct Scanner {
  bool hasNext = 1;
  bool hasRead = 1;
  int nextInt() {
    hasRead = 0;
    int res = 0;
    char flag = 1, ch = getchar();
    while (ch != EOF && !isdigit(ch)) {
      hasRead = 1;
      flag = (ch == '-') ? -flag : flag;
      ch = getchar();
    }
    while (ch != EOF && isdigit(ch)) {
      hasRead = 1;
      res = res * 10 + (ch - '0');
      ch = getchar();
    }
    if (ch == EOF) hasNext = 0;
    return res * flag;
  }
  long long nextLL() {
    hasRead = 0;
    long long res = 0;
    char flag = 1, ch = getchar();
    while (ch != EOF && !isdigit(ch)) {
      hasRead = 1;
      flag = (ch == '-') ? -flag : flag;
      ch = getchar();
    }
    while (ch != EOF && isdigit(ch)) {
      hasRead = 1;
      res = res * 10 + (ch - '0');
      ch = getchar();
    }
    if (ch == EOF) hasNext = 0;
    return res * flag;
  }
  char nextChar() {
    hasRead = 0;
    char ch = getchar();
    while (ch != EOF && isspace(ch)) {
      hasRead = 1;
      ch = getchar();
    }
    if (ch == EOF) hasNext = 0;
    return ch;
  }
  int nextString(char *str) {
    hasRead = 0;
    int len = 0;
    char ch = getchar();
    while (ch != EOF && isspace(ch)) {
      hasRead = 1;
      ch = getchar();
    }
    while (ch != EOF && !isspace(ch)) {
      hasRead = 1;
      str[++len] = ch;
      ch = getchar();
    }
    str[len + 1] = 0;
    if (ch == EOF) hasNext = 0;
    return len;
  }
} sc;
long long rd() {
  long long x = sc.nextLL();
  return x;
}
void rd(int &x) { x = sc.nextInt(); }
void rd(long long &x) { x = sc.nextLL(); }
void rd(char &x) { x = sc.nextChar(); }
void rd(char *x) { sc.nextString(x); }
template <typename T1, typename T2>
void rd(pair<T1, T2> &x) {
  rd(x.first);
  rd(x.second);
}
template <typename T>
void rd(T *x, int n) {
  for (int i = 1; i <= n; ++i) rd(x[i]);
}
void printInt(int x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x >= 10) printInt(x / 10);
  putchar('0' + x % 10);
}
void printLL(long long x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x >= 10) printLL(x / 10);
  putchar('0' + x % 10);
}
void pr(int x, char ch = '\n') {
  printInt(x);
  putchar(ch);
}
void pr(long long x, char ch = '\n') {
  printLL(x);
  putchar(ch);
}
template <typename T1, typename T2>
void pr(pair<T1, T2> x, char ch = '\n') {
  pr(x.first, ' ');
  pr(x.second, ch);
}
template <typename T>
void pr(T *x, int n) {
  for (int i = 1; i <= n; ++i) pr(x[i], " \n"[i == n]);
}
template <typename T>
void pr(vector<T> &x) {
  int n = x.size();
  for (int i = 1; i <= n; ++i) pr(x[i - 1], " \n"[i == n]);
}
template <typename T>
void cmin(T &x, T y) {
  if (y < x) x = y;
}
template <typename T>
void cmax(T &x, T y) {
  if (y > x) x = y;
}
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double PI = acos(-1.0);
const double EPS = 1e-9;
const int MOD = 1000000007;
int n;
int a[200005];
vector<int> S;
vector<int> val;
void show() {
  puts("---");
  int siz = S.size();
  for (int i = siz - 1; i >= 0; --i) printf("%d ", S[i]);
  printf("\n");
  for (int i = siz - 1; i >= 0; --i) printf("%d ", val[i]);
  printf("\n");
}
struct Solver {
  void InitOnce() {}
  void Read() {
    rd(n);
    rd(a, n);
  }
  void Solve() {
    if (is_sorted(a + 1, a + 1 + n)) {
      puts("0");
      return;
    }
    int ans = 0;
    while (!is_sorted(a + 1, a + 1 + n)) {
      S.clear();
      val.clear();
      for (int i = n; i >= 1; --i) {
        int curval = 0;
        while (!S.empty() && a[i] > S.back()) {
          if (curval >= val.back())
            ++curval;
          else
            curval = val.back();
          S.pop_back();
          val.pop_back();
          cmax(ans, curval);
        }
        S.push_back(a[i]);
        val.push_back(curval);
      }
      n = S.size();
      for (int i = 1; i <= n; ++i) a[n + 1 - i] = S[i - 1];
    }
    pr(ans);
  }
} solver;
int main() {
  solver.InitOnce();
  int t = 1;
  t = INF;
  while (t--) {
    solver.Read();
    if (!sc.hasRead) break;
    solver.Solve();
    if (!sc.hasNext) break;
  }
  return 0;
}

```