Home Web Board ProblemSet Standing Status Statistics
1.该OJ由于交换空间受限,暂不不支持万能头文件:bits/stdc++.h!!! 2.该OJ如果是长整型的话,C的输入输出请使用%lld!!!
Problem C: 多少黄昏烟雨斜檐,翻开此题,拿起就是AC

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

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 52  Solved: 7
[Submit][Status][Web Board]

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

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

Sample Output

3

HINT


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



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



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



所以输出为3

[Submit][Status][Web Board]