题目描述

设 $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}$。称下标 $i = [1..N]$ 是 热 的，当且仅当存在一个序列 $A'_{1..N}$ 满足以下条件：

• $A'_i \ne A_i$，且 $A'_i$ 是 $[-100\,000, 100\,000]$ 内的整数；
• 对于所有 $j \ne 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$ → $A'_{1..5} = [30, 1, 0, 7, 2]$ → $sun([30, 1, 0, 7, 2], 5) = [0]$
• $i = 3$，$A'_1 = -78\,600$ → $A'_{1..5} = [4, 1, -78\,600, 7, 2]$ → $sun([4, 1, -78\,600, 7, 2], 5) = [-471\,626]$
• $i = 5$，$A'_1 = 28$ → $A'_{1..5} = [4, 1, 0, 7, 28]$ → $sun([4, 1, 0, 7, 28], 5) = [0]$

注意，$0$ 和 $-471\,626$ 都是 $235\,813$ 的倍数。另一方面，下标 $i = 2$ 不是热的，因为不存在满足条件的整数 $A'_2 \ne A_2$ 在 $[-100\,000, 100\,000]$ 内，使得 $sun(A'_{1..5}, 5)$ 的唯一元素是 $235\,813$ 的倍数。下标 $i = 4$ 同样不是热的。

输入格式

输入第一行包含一个整数 $N$（$1 \leq N \leq 100\,000$），表示序列 $A$ 中整数的个数。下一行包含 $N$ 个整数 $A_i$（$-100\,000 \leq A_i \leq 100\,000$），表示整数序列。

输出格式

输出一行一个整数，表示给定 $A_{1..N}$ 中热下标的个数。

5
4 1 0 7 2

3

4
10 20 30 -40

4

2
100 100

0

提示

样例 #1 解释

这是题目描述中的例子。

样例 #2 解释

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

翻译由 DeepSeek 完成