Problem B: 多少黄昏烟雨斜檐,翻开此题,拿起就是AC

Problem B: 多少黄昏烟雨斜檐,翻开此题,拿起就是AC

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 4  Solved: 3
[Submit] [Status] [Web Board] [Creator:]

Description

         小平头是一个聪明的ACMer,他很喜欢数学,觉得数学题都非常简单。小平头有一个奇怪的怪癖,因为他是一个处女座直男。他喜欢等差数列这样间距相同的数列,而不喜欢等比数列。现在有一个长度为n的数列,假设你是小平头,让你求出这个数列最少的等差数列个数。

Input

         第一行输入一个n,代表此数列有n个数(1 <= n <= 2*10^5);

         第二行输入n个数a[1],a[2],a[3]…..a[n]( 1 <= a[i] <= 10^9 或者 a[i] = -1 ),当a[i] = -1 时代表数列中这个数的值未知但是一定大于0。

Output

         输出最少等差数列的个数。

Sample Input Copy

9
-1  6  -1  2  -1  4  7  -1  2

Sample Output Copy

3

HINT

第一个-1的值为8,第二个-1的值为4,然后构成等差数列8 6 4 2

第三个-1的值为1,构成等差数列1 4 7

第四个-1的值为任意数,均可和2构成等差数列

所以输出为3