1347. 环中环 (Standard IO)

Description

　　被认为天才的小头遇到麻烦了！！这天数学课老师给出了一道难题，而小头居然没能在3秒内解决，可见此题难度之大。 　　问题是这样的：n个整数围成一个环，老师要求选出其中的若干数，使得选中的数所组成的环中，两个相邻数的差的绝对值不等于1。在满足这个前提下，问最多能取多少个数。

Input

　　第一行一个正整数n，表示有n个数 　　第二行n个整数，a1、a2……an 按顺时针方向围成一个环。

Output

　　一个正整数，即表示最多能选多少个数。

Sample Input

5

1 2 3 5 2

Sample Output

3

【样例解释】

　　 最多能选3个数 　　 既选择（1，3，5）或者（2，5，2）

【数据范围】

　　 30%的数据，n≤10 　　 50%的数据，n≤100 　　 70%的数据，n≤1000 　　 100%的数据，n≤100000，ai≤1100000

题解

代码