Johnny 买了一台 3D 打印机。他想在一个简单的任务上测试它：按给定顺序打印 $n$ 个底面为相同正方形且高度分别为 $1, 2, \dots, n$ 的长方体。打印机通过从左到右和从右到左的扫描（sweep）来工作，这些扫描可以任意混合，即可以连续执行两次从左到右的扫描，从右到左也是如此。在一次扫描中，打印机可以在任意数量的位置停下并在每个位置上打印一个长方体；打印的第一个长方体具有给定的高度，之后打印的每一个长方体的高度都比前一个低 $1$（因为打印头会冷却）。打印机不能在已经打印过东西的位置上再次打印。每次扫描都需要花费资金。请帮助 Johnny 最小化完成该任务所需的扫描次数。

输入格式

输入第一行包含一个正整数 $n$ ($1 \le n \le 10^6$)，表示需要打印的长方体数量。

第二行（也是最后一行）包含一个由 $n$ 个两两不同的正整数组成的序列 $a_i$ ($1 \le a_i \le n$)。这些是待打印的连续长方体的高度。

输出格式

输出一个正整数：打印给定长方体序列所需的最小扫描次数。

样例

输入样例 1

6
3 2 4 1 5 6

输出样例 1

2

输入样例 2

8
8 7 4 1 5 2 3 6

输出样例 2

3

说明

在第一个样例中，Johnny 可以在一次从右到左的扫描中打印高度为 $6, 5, 4, 3$ 的长方体，并在一次从左到右的扫描中打印高度为 $2, 1$ 的长方体。

在第二个样例中，Johnny 可以在一次从左到右的扫描中打印高度为 $8, 7, 6$ 的长方体，然后通过一次从右到左的扫描打印 $5, 4$，最后再通过一次从右到左的扫描打印 $3, 2, 1$。