题目描述

小 F 在做梦时得到了一个神秘函数 $\phi(x)$，这是一个连续函数。

零点 $x=x_0$ 是一系列特殊的数，使得 $\phi(x_0)=0$，很可惜的是，$\phi(x)$ 函数相当复杂，无法精确计算其零点。

零点存在定理

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

小 F 计算了 $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$。在 $(0,1)$，$(2,3)$，$(3,4)$ 上各至少有一个零点。

• $\phi(0) \times \phi(1) = -2 < 0$，按照零点存在定理，在 $0 < x < 1$ 的区域一定会有至少一个零点。
• $\phi(1) \times \phi(2) = 3 > 0$，无法保证在 $1 < x < 2$ 的区域存在零点。
• $\phi(2) \times \phi(3) = -6 < 0$，按照零点存在定理，在 $2 < x < 3$ 的区域一定会有至少一个零点。
• $\phi(3) \times \phi(4) = -2 < 0$，按照零点存在定理，在 $3 < x < 4$ 的区域一定会有至少一个零点。
• $\phi(4) \times \phi(5) = 2 > 0$，无法保证在 $4 < x < 5$ 的区域存在零点。

故至少能保证有 $3$ 个零点。

数据规模与约定

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