P15591 [ICPC 2020 Jakarta R] 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(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}$.

#### 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]$