题目描述

给定一个连续函数 $\phi(x)$，其零点 $x_0$ 满足 $\phi(x_0) = 0$。

> 零点存在定理
>
> 若 $\phi(a) \cdot \phi(b) \lt 0$，则在区间 $(a, b)$ 内，函数 $\phi(x)$ 至少存在一个零点。

已知 $0 \sim N$ 范围内每个整数点 $w$ 的函数值 $\phi(w)$，利用零点存在定理，求在 $(0, N)$ 范围内 $\phi(x)$ 至少有多少个零点。

输入格式

输入共两行。

第一行一个整数 $N$。

第二行 $N+1$ 个整数，依次为 $\phi(0), \phi(1), \cdots, \phi(N)$。

保证第二行中所有数据不为 $0$。

输出格式

输出一行一个整数，表示在 $(0, N)$ 上 $\phi(x)$ 至少有多少个零点。

样例

5
-2 1 3 -2 1 2

3

提示

样例 1 说明

$\phi(0) = -2, \phi(1) = 1, \phi(2) = 3, \phi(3) = -2, \phi(4) = 1, \phi(5) = 2$。

• $\phi(0) \times \phi(1) = -2 \lt 0$，区间 $(0, 1)$ 至少有一个零点。
• $\phi(1) \times \phi(2) = 3 \gt 0$，无法确定。
• $\phi(2) \times \phi(3) = -6 \lt 0$，区间 $(2, 3)$ 至少有一个零点。
• $\phi(3) \times \phi(4) = -2 \lt 0$，区间 $(3, 4)$ 至少有一个零点。
• $\phi(4) \times \phi(5) = 2 \gt 0$，无法确定。

故至少有 $3$ 个零点。

数据规模与约定

• 对于 $30\%$ 的数据，$1 \le N \le 5000$，$\phi(i) \in \{-1, 1\}$。
• 对于 $100\%$ 的数据，$1 \le N \le 10^5$，$0 \lt |\phi(i)| \le 10^9$。