CF416D Population Size

Polycarpus 对等差数列和世界万物之间的相互关系发展出了一种有趣的理论。他当前的想法是，Berland 首都的人口随时间变化如同一个等差数列，或者说是多个等差数列。 Polycarpus 认为，如果他把首都连续几年的总人口按照顺序记为 $a_1, a_2, ..., a_n$，那么可以把该序列看作是若干个等差数列依次拼接而成。例如，序列 $(8,6,4,2,1,4,7,10,2)$ 可以看作是三个等差数列 $(8,6,4,2)$，$(1,4,7,10)$ 以及 $(2)$ 顺次连接得到的。 然而，不幸的是，并不是每一年都有人口普查，因此 $n$ 年连续年份的人口数据并不总是全部已知。有些 $a_i$ 的值是未知的，用 $-1$ 表示。 给定一个由正整数和 $-1$ 组成的序列 $a=(a_1,a_2,\ldots,a_n)$，请你计算，为了得到 $a$，Polycarpus 至少需要写多少个等差数列依次拼接后才能获得 $a$。这些等差数列可以按照顺序逐个拼接。对于 $a$ 中等于 $-1$ 位置的数，它们可以被任意正整数替换，但 $a_i>0$ 的位置必须等于等差数列中相应元素的取值。 需要注意的是，有限长度的序列 $c$，如果任意相邻两项的差 $c_{i+1}-c_i$ 是常数，那么称 $c$ 是等差数列。根据定义，任意长度为 $1$ 的序列也被视为等差数列。

输入的第一行包含整数 $n$（$1 \leq n \leq 2\cdot 10^{5}$），表示序列的长度。 第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$，用空格分隔，$1 \leq a_i \leq 10^9$ 或 $a_i = -1$。

输出一个整数，表示你至少需要多少个等差数列依次拼接，才能得到序列 $a$。$a$ 中的 $-1$ 可以用任意正整数替换，且 $a_i>0$ 的位置必须与相应的等差数列元素一致。

由 ChatGPT 5 翻译