20687번 - Moon and Sun 다국어

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\left(S_{1\dots|S|}\right) = \begin{cases} S & \text{if } |S| = 1 \\ \left[ S_2 − S_1, S_3 − S_2, \dots , S_{|S|} − S_{|S|−1} \right] & \text{if }|S| > 1 \end{cases}$$

$$sun\left(S_{1\dots|S|}, K\right) = \begin{cases} S & \text{if } K = 1 \\ sun\left(moon\left(S_1\dots|S|\right), K − 1\right) & \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\left(S_{1\dots |S|}, |S|\right)$ is always a sequence with exactly one element.

You are given a sequence of $N$ integers $A_{1\dots N}$. An index $i = [1\dots N]$ is hot if and only if there exists a sequence $A'_{1\dots 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\left(A'_{1\dots N}, N\right)$ is a multiple of $235 813$.

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

For example, there are $3$ hot indices in $A_{1\dots 5} = [4, 1, 0, 7, 2]$, which are $\{1, 3, 5\}$.

• $i = 1 ~~ A'_1 = 30 \rightarrow A'_{1\dots5} = [30, 1, 0, 7, 2] \rightarrow sun([30, 1, 0, 7, 2], 5) = [0]$
• $i = 3 ~~ A'_1 = −78 600 \rightarrow A'_{1\dots5} = [4, 1, −78 600, 7, 2] \rightarrow sun([4, 1, −78 600, 7, 2], 5) = [−471 626]$
• $i = 5 ~~ A'_1 = 28 \rightarrow A'_{1\dots5} = [4, 1, 0, 7, 28] \rightarrow 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\dots 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 \le N \le 100 000$) representing the number of integers in $A$. The next line contains $N$ integers: $A_i$ ($-100 000 \le A_i \le 100 000$) representing the sequence of integers.

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