题目描述

未来人工智能时代到来了，机器人已经遍布整个工厂。工厂的传送带上依次排列着 $N$个机器人，其中，第$i$ 个机器人的质量为 $Ai$。经过仔细观察，发现：

1.来自同一个家族的机器人，在这 $N$ 个机器人中一定是连续的一段。

2.如果从第 $i$ 个机器人到第 $j$ 个机器人都来自同一个家族，那么 $Ai$ 到 $Aj$ 从小到大排序后一定是公差大于 $1$的等差数列的子序列。

OpenAI 发现，不同家族的个数越少，机器人就会越团结，成功逃离工厂的概率就会越高。我们想知道，这 $N$个机器人最少来自几个不同的家族呢？

输入格式

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

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

输出格式

一行一个正整数，表示答案。

7
1 5 11 2 6 4 7

3

说明

1 5 11 是等差数列{1,3,5,7,9,11}的子序列， 2 4 6 是等差数列{2,4,6,8}的子序列， 7 是等差数列{7,9,11}的子序列。

8
4 2 6 8 5 3 1 7

2

说明

2 4 6 8 是等差数列{2,4,6,8}的子序列， 1 3 5 7 是等差数列{1,3,5,7}的子序列。

数据规模与约定

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