[语言月赛 202312] 函数零点

小 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)$ **至少**有多少零点？ ## Input 输入共两行。 输入的第一行为一个整数 $N$。 输入的第二行为 $N+1$ 个整数，依次代表 $\phi(0),\phi(1),\cdots,\phi(N)$。 **保证第二行中所有数据不为 $0$**。 ## Output 输出一行一个整数，代表在 $(0,N)$ 上，$\phi(x)$ 至少有多少个零点。 [samples] ## Note ### 样例 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$。