AlanashKO 热爱金钱。在新年前夕，他得到了 $N$ 张钞票。每张钞票的面值都是一个正整数。在玩耍时，AlanashKO 将所有钞票排成一行，并从左到右依次编号为 $1$ 到 $N$。随后，他决定将所有钞票按非递减顺序排序。为此，AlanashKO 执行以下操作：首先，他将钞票分成一个或多个不相交的子段，且每张钞票都属于某个子段。然后，所有子段按从左到右的顺序依次插入到新的一行中，即先插入最左侧的子段（第一个子段），然后插入下一个最左侧的子段，依此类推。每个子段要么插入到当前新行中任意两张钞票之间，要么插入到当前新行的两端之一。子段内钞票的顺序在插入时不会改变。

AlanashKO 希望最小化子段的数量，以便他最终能将钞票按非递减顺序排序。请帮助他找到这个值。

输入格式

第一行包含一个正整数 $N$ ($1 \le N \le 10^6$)，表示钞票的数量。第二行包含 $N$ 个正整数 $a_i$ ($1 \le a_i \le 10^6$)，表示第 $i$ 张钞票的面值。

输出格式

输出一行，包含一个整数，表示允许 AlanashKO 将钞票排序所需的最小子段数量。

子任务

本题包含四个子任务：

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 个子段：$|3\ 6|4\ 5|1\ 2|$（竖线表示子段边界）。 第一步后：初始行变为 $|4\ 5|1\ 2|$，新行变为 $|3\ 6|$。 第二步，将子段 $|4\ 5|$ 插入到 $3$ 和 $6$ 之间。 第二步后：初始行变为 $|1\ 2|$，新行变为 $|3\ 4\ 5\ 6|$。 然后，将子段 $|1\ 2|$ 插入到新行的开头，结果为 $|1\ 2\ 3\ 4\ 5\ 6|$。