题目描述

有一排砖，白砖记为 $0$，黑砖记为 $1$。要把整排砖划分为若干个非空连续段，使各段白砖与黑砖的数量比例相同。求最多能分成多少段。某种颜色完全没有时，比例允许为 $0:1$ 或 $1:0$。

输入格式

第一行整数 $N$。接下来 $N$ 行，每行两个整数 $K_i,C_i$，表示在当前砖排末尾添加 $K_i$ 块颜色为 $C_i$ 的砖。相邻两行可以是同一种颜色。

输出格式

输出最多分段数。

样例

3
1 1
3 0
2 1

2

4
3 0
3 1
9 0
1 1

3

数据范围

对于30%的数据，$N=1$；对于60%的数据，所有 $K_i$ 相等；对于100%的数据，$1\le N\le10^5$，$1\le K_i\le10^9$，$C_i\in\{0,1\}$，砖块总数不超过 $10^9$。