U241855 2021年9月海淀区赛小学组T5-区间划分

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

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

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

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

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