题目描述

Let $S$ be a non-empty sequence of integers and $K$ be a positive integer. The functions $moon()$ and $sun()$ are defined as follows.

$$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} $$

For example,

• $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]$.

Observe that $sun(S_{1..|S|}, |S|)$ is always a sequence with exactly one element.

You are given a sequence of $N$ integers $A_{1..N}$. An index $i = [1..N]$ is hot if and only if there exists a sequence $A'_{1..N}$ satisfying the following conditions:

• $A'_i \ne A_i$ and $A'_i$ is an integer between $-100\,000$ and $100\,000$, inclusive;
• $A'_j = A_j$ for all $j \ne i$;
• The only element in $sun(A'_{1..N}, N)$ is a multiple of $235\,813$.

Your task in this problem is to count the number of hot indices in a given $A_{1..N}$.

For example, there are $3$ hot indices in $A_{1..5} = [4, 1, 0, 7, 2]$, which are $\{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]$

Note that both $0$ and $-471\,626$ are multiples of $235\,813$. On the other hand, the index $i = 2$ is not hot as there does not exist an integer $A'_2 \ne A_2$ between $-100\,000$ and $100\,000$, inclusive, such that the only element in $sun(A'_{1..5}, 5)$ is a multiple of $235\,813$. The index $i = 4$ is also not hot for a similar reason.

输入格式

Input begins with a line containing an integer: $N$ ($1 \leq N \leq 100\,000$) representing the number of integers in $A$. The next line contains $N$ integers: $A_i$ ($-100\,000 \leq A_i \leq 100\,000$) representing the sequence of integers.

输出格式

Output in a line an integer representing the number of hot indices in the given $A_{1..N}$.

5
4 1 0 7 2

3

4
10 20 30 -40

4

2
100 100

0

提示

Explanation for the sample input/output #1

This is the example from the problem description.

Explanation for the sample input/output #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]$