6125: 2021年9月海淀区中小学信息学竞赛 （小学组）T5 —— 区间划分（divide）
[Creator : ]
Description
$N$ 个数组成序列 $\{A_i\}$，求该序列最小可以划分成多少个区间，某个 $[i,\ j]$ 区间中的数 $A_i$ 到 $A_j$ 从小到大排序后一定是公差大于 $1$ 的等差数列的子序列。
Input
第一行一个正整数 $N$。
接下来一个行包括 $N$ 个正整数，第 $i$ 个正整数为 $A_i$。
接下来一个行包括 $N$ 个正整数，第 $i$ 个正整数为 $A_i$。
Output
仅有一个正整数，表示最少可以被划分的区间数。
Constraints
对于 $20\%$ 的数据，$N \leq 10$。
对于 $40\%$ 的数据，$N \leq 100$。
对于 $60\%$ 的数据，$N \leq 1,000,\ 1 \leq A_i \leq 10^6$。
另外 $20\%$ 的数据满足，$A_i$ 互不相同。
对于 $100\%$ 的数据，$N \leq 100,000,\ 1 \leq A_i \leq 10^9$。
对于 $40\%$ 的数据，$N \leq 100$。
对于 $60\%$ 的数据，$N \leq 1,000,\ 1 \leq A_i \leq 10^6$。
另外 $20\%$ 的数据满足，$A_i$ 互不相同。
对于 $100\%$ 的数据，$N \leq 100,000,\ 1 \leq A_i \leq 10^9$。
Sample 1 Input
7
1 5 11 2 6 4 7
Sample 1 Output
3
Sample 2 Input
8
4 2 6 8 5 3 1 7
Sample 2 Output
2
将 $[1,\ 4]$ 划分为一个区间，对应的数 $A_1$ 到 $A_4$ 排序后为 $\{2,\ 4,\ 6,\ 8\}$，公差为 $2$。
将 $[5,\ 8]$ 划分为一个区间，对应的数 $A_5$ 到 $A_8$ 排序后为 $\{1,\ 3,\ 5,\ 7\}$，公差为 $2$。
将 $[5,\ 8]$ 划分为一个区间，对应的数 $A_5$ 到 $A_8$ 排序后为 $\{1,\ 3,\ 5,\ 7\}$，公差为 $2$。