题目描述

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

输入格式

第一行一个正整数 $N$

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

数据范围

对于 20% 的数据满足，N <=10

40% 的数据满足，N <=100

60% 的数据满足，N<=1000 , 1 <= $A_i$ <= $10^6$

另有 20% 的数据满足，$A_i$ 互不相同。

100% 的数据满足，N <= 100000 , 1 <= $A_i$ < $10^9$

输出格式

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

样例

7
1 5 11 2 6 4 7

3

8
4 2 6 8 5 3 1 7

2