← 返回题目列表

Codeforces · 416/D

D. 人口规模

中文机器翻译题面 查看原题

波利卡普斯(Polycarpus)发展了一种关于算术级数与世界上一切事物之间相互关系的有趣理论。他目前的想法是,贝尔兰首都的人口随着时间的推移像算术级数一样变化。嗯,或者像多个算术级数一样。

波利卡普斯认为,如果他以序列 a1, a2, ..., an 的形式写出连续几年的首都人口,那么可以方便地将数组视为几个算术级数,一个接一个地写出。例如,序列(8,6,4,2,1,4,7,10,2)可以被认为是由三个等差数列(8,6,4,2),(1,4,7,10)和(2)依次写成的序列。

不幸的是,Polycarpus 可能没有连续 n 年的所有数据(毕竟人口普查不会每年进行)。因此,ai 的某些值可能是未知的。这些值由数字-1 表示。

对于给定的序列 a = (a1, a2, ..., an),由正整数和值 -1 组成,求 Polycarpus 需要得到 a 的最小算术级数数。为了得到a,需要将级数逐个写下来。值 -1 可以对应于任意正整数,并且值 ai > 0 必须等于所查找的级数连续记录的相应元素。

让我们提醒您,如果有限序列 c 中任意两个连续元素的差 ci + 1 - ci 恒定,则该序列 c 称为算术级数。根据定义,任何长度为 1 的序列都是算术级数。

输入

输入的第一行包含整数 n (1 ≤ n ≤ 2·105) — 序列中的元素数量。第二行包含整数值 a1、a2、...、an,以空格分隔(1 ≤ ai ≤ 109 或 ai = - 1)。

输出

打印为得到序列 a 需要依次写入的算术级数的最小数量。 a中标记为-1的位置可以用任意正整数表示。

示例

输入 #1

9
8 6 4 2 1 4 7 10 2

输出 #1

3

输入 #2

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

输出 #2

3

输入 #3

5
-1 -1 -1 -1 -1

输出 #3

1

输入#4

7
-1 -1 4 5 1 2 3

输出#4

2