题目描述

小 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)$ 至少有多少个零点。

样例 #1

样例输入 #1

5
-2 1 3 -2 1 2

样例输出 #1

3

提示

样例解释

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

• $\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)|\le 10^9$。