AlanashKO はお金が大好きです。大晦日に、彼は $N$ 枚の紙幣をもらいました。各紙幣の額面は正の整数です。遊んでいるうちに、AlanashKO はすべての紙幣を一列に並べ、左から右へ $1$ から $N$ までの番号を付けました。そして、すべての紙幣を額面の非減少順に並べ替えることにしました。

そのために AlanashKO は次の手順を行います。まず、紙幣の列を、互いに重ならない $1$ 個以上の区間に分割します。各紙幣はいずれかの区間に属します。その後、各区間を左から右の順に、新しい列へ順番に挿入します。つまり、最初に最も左の区間（第 $1$ 区間）を挿入し、その次に残りのうち最も左の区間を挿入する、という操作を続けます。各区間は、その時点の新しい列にある任意の隣り合う $2$ 枚の紙幣の間、または列の両端のいずれかに挿入できます。挿入するとき、区間内の紙幣の順序は変わりません。

AlanashKO は、最終的に紙幣を非減少順に並べ替えられるようにするための区間数を最小にしたいと考えています。この値を求めるのを手伝ってください。

入力

最初の行には、紙幣の枚数を表す正の整数 $N$（$1 \le N \le 10^6$）が $1$ 個与えられます。次の行には、$i$ 番目の紙幣の額面を表す $N$ 個の正の整数 $a_i$（$1 \le a_i \le 10^6$）が与えられます。

出力

AlanashKO が紙幣を並べ替えられるようにするための最小の区間数を表す整数を、$1$ 行に出力してください。

小課題

この問題には次の $4$ つの小課題があります。

1. $N \le 8$。$9$ 点。
2. $N \le 20$。$16$ 点。
3. $N \le 300$。$20$ 点。
4. $N \le 10^6$。$55$ 点。

各小課題の得点は、それより前のすべての小課題に正解した場合にのみ与えられます。

入出力例

入力 1

6
3 6 4 5 1 2

出力 1

3

注記

区間とは、連続する部分列のことです。

入出力例を考えてみましょう。

最小の答えは、|3 6|4 5|1 2| のように $3$ 個の区間に分割する場合です（縦棒は区間の境界を表します）。

第 $1$ 段階の後、元の列は |4 5|1 2|、新しい列は |3 6| です。

第 $2$ 段階では、区間 |4 5| を $3$ と $6$ の間に挿入します。

第 $2$ 段階の後、元の列は |1 2|、新しい列は |3 4 5 6| です。

その後、区間 |1 2| を新しい列の先頭に挿入すると、|1 2 3 4 5 6| が得られます。