设 $S$ 为一个非空整数序列，$K$ 为一个正整数。函数 $moon()$ 和 $sun()$ 定义如下：

$$moon(S_{1..|S|}) = \begin{cases} S & \text{if } |S| = 1 \\ [S_2 - S_1, S_3 - S_2, \dots, S_{|S|} - S_{|S|-1}] & \text{if } |S| > 1 \end{cases}$$

$$sun(S_{1..|S|}, K) = \begin{cases} S & \text{if } K = 1 \\ sun(moon(S_{1..|S|}), K - 1) & \text{if } K > 1 \end{cases}$$

例如： $moon([2, 7]) = [5]$。 $moon([4, 1, 0, 7, 2]) = [-3, -1, 7, -5]$。 * $sun([4, 1, 0, 7, 2], 5) = sun([-3, -1, 7, -5], 4) = sun([2, 8, -12], 3) = sun([6, -20], 2) = sun([-26], 1) = [-26]$。

观察可知，$sun(S_{1..|S|}, |S|)$ 始终是一个仅包含一个元素的序列。

给定一个包含 $N$ 个整数的序列 $A_{1..N}$。当且仅当存在一个序列 $A'_{1..N}$ 满足以下条件时，称索引 $i \in [1..N]$ 是“热”的： $A'_i \neq A_i$，且 $A'_i$ 是一个介于 $-100\,000$ 到 $100\,000$ 之间的整数（包含边界）； 对于所有 $j \neq i$，满足 $A'_j = A_j$； * $sun(A'_{1..N}, N)$ 中的唯一元素是 $235\,813$ 的倍数。

你的任务是计算给定序列 $A_{1..N}$ 中“热”索引的数量。

例如，在 $A_{1..5} = [4, 1, 0, 7, 2]$ 中有 3 个热索引，分别是 $\{1, 3, 5\}$。 $i = 1, A'_1 = 30 \to A'_{1..5} = [30, 1, 0, 7, 2] \to sun([30, 1, 0, 7, 2], 5) = [0]$ $i = 3, A'_1 = -78\,600 \to A'_{1..5} = [4, 1, -78\,600, 7, 2] \to sun([4, 1, -78\,600, 7, 2], 5) = [-471\,626]$ * $i = 5, A'_1 = 28 \to A'_{1..5} = [4, 1, 0, 7, 28] \to sun([4, 1, 0, 7, 28], 5) = [0]$

注意 $0$ 和 $-471\,626$ 都是 $235\,813$ 的倍数。另一方面，索引 $i = 2$ 不是热的，因为不存在一个介于 $-100\,000$ 到 $100\,000$ 之间的整数 $A'_2 \neq A_2$，使得 $sun(A'_{1..5}, 5)$ 中的唯一元素是 $235\,813$ 的倍数。索引 $i = 4$ 也因同样的原因不是热的。

输入格式

输入的第一行包含一个整数 $N$ ($1 \le N \le 100\,000$)，表示序列 $A$ 中整数的个数。下一行包含 $N$ 个整数：$A_i$ ($-100\,000 \le A_i \le 100\,000$)，表示该整数序列。

输出格式

输出一行，包含一个整数，表示给定序列 $A_{1..N}$ 中热索引的数量。

样例

样例输入 1

5
4 1 0 7 2

样例输出 1

3

说明 1

这是题目描述中的示例。

样例输入 2

4
10 20 30 -40

样例输出 2

4

说明 2

• $i = 1, A'_1 = -70 \to A'_{1..4} = [-70, 20, 30, -40] \to sun([-70, 20, 30, -40], 4) = [0]$
• $i = 2, A'_2 = 78\,651 \to A'_{1..4} = [10, 78\,651, 30, -40] \to sun([10, 78\,651, 30, -40], 4) = [235\,813]$
• $i = 3, A'_3 = -78\,601 \to A'_{1..4} = [10, 20, -78\,601, -40] \to sun([10, 20, -78\,601, -40], 4) = [235\,813]$
• $i = 4, A'_4 = 40 \to A'_{1..4} = [10, 20, 30, 40] \to sun([10, 20, 30, 40], 4) = [0]$

样例输入 3

2
100 100

样例输出 3

0