Description

$N$ 个数组成序列 $\{Ai\}$，求该序列最少可以划分成多少个区间，某个$[i,j]$区间中的数 $Ai$ 到 $Aj$ 从小到大排序 后一定是 公差大于 1 的等差数列的 子序列 。

Input Format

第一行一个正整数 $N$。

接下来一行包含 $N$ 个正整数，第 $i$ 个正整数为 $Ai$。

Output Format

仅有一个正整数，表示最少可以被划分的区间数。

7
1 5 11 2 6 4 7

3

8
4 2 6 8 5 3 1 7

2

Hint

数据范围：

对于 $20$% 的数据满足，$N≤10$。 $40$%的数据满足，$N≤100$。 $60$%的数据满足，$N≤1000，1≤Ai≤10^6$。 另有 $20$%的数据满足，$Ai$ 互不相同。 ​$100$%的数据满足，$N≤100000，1≤Ai≤10^9$。