You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

对于给定的长度为 $n$ 的整数序列，求该序列最少可以被划分成多少个区间，使得每个区间都是等差数列。

例如，有一个序列 $8,6,4,2,1,4,7,10,2$ ，最少可被划分为三个区间 $(8,6,4,2)$ , $(1,4,7,10)$ 和 $(2)$ 。

如果给定的序列中有 $-1$ ，则可以根据需要将其替换成任意正整数。

Input Format

第一行仅有一个正整数 $n$ ，第二行包含个数 $a_{1},a_{2},...,a_{n}$ ( $1\le a_i\le 10^9$ 或 $a_i=-1$ )。

Output Format

仅有一个正整数，表示最少可以被划分的区间数。

9
8 6 4 2 1 4 7 10 2

3

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

3

5
-1 -1 -1 -1 -1

1

7
-1 -1 4 5 1 2 3

2

Hint

数据范围：

​ 对于 $10\%$ 的数据 $n \le 1000$ ，没有 $-1$； ​ 对另外 $20\%$ 的数据 $1\le n\le 2\times 10^{5}$ ，没有连续的 $-1$； ​ 对于另外的 $70\%$ 数据 $1\le n\le 2\times 10^{5}$ ，有很多个 $-1$ ； ​ 对于$100\%$的数据，$1\le n\le 2\times 10^{5}$ 。