问题 23838 --Seq

23838: Seq

时间限制: 1 Sec  内存限制: 128 MB
提交: 60  解决: 9
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][19648kb]

题目描述

给出数列a,ai表示数列里第i个数。
现在需要你找出a中最长的X链,X链是什么呢,就是X链中相邻的两个数不能够是差为1的两个数。X链应该是a中的子序列。
简单来说 1 2 3 4 5 中最长的X链就是 1 3 5.

输入

第一行给出N,告诉你a的长度。
下面一行N个整数,分别代表ai。 1<= ai <= 100000

输出

输出最长X链的长度。

样例输入

10
1 2 3 4 5 6 7 8 9 10

样例输出

5

提示

【数据范围】

告诉你N<1000开心不? 可惜是30%

其实也不大N<100000。不过呢还是小了点,这样只有60%

最后不过是N<1000000。

来源

[提交][状态]