Moon and Sun

문제

Let $SS$ be a non-empty sequence of integers and $KK$ be a positive integer. The functions $moon()moon()$ and $sun()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([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\dots \mathrm{\mid }S\mathrm{\mid }},\mathrm{\mid }S\mathrm{\mid })sun\backslash left(S\_\{1\backslash dots\; |S|\},\; |S|\backslash right)$ is always a sequence with exactly one element.

You are given a sequence of $NN$ integers $A_{1\dots N}A\_\{1\backslash dots\; N\}$. An index $i=[1\dots N]i\; =\; [1\backslash dots\; N]$ is hot if and only if there exists a sequence $A_{1\dots N}^{\mathrm{\prime }}A\text{'}\_\{1\backslash dots\; N\}$ satisfying the following conditions.

• $A_i^{\mathrm{\prime }}\mathrm{\ne }{A}_{i}A\text{'}\_i\; \backslash ne\; A\_i$ and $A_i^{\mathrm{\prime }}A\_i\text{'}$ is an integer between $-100000-100\; 000$ and $100000100\; 000$, inclusive;
• $A_j^{\mathrm{\prime }}=A_{j}A\text{'}\_j\; =\; A\_j$ for all $j\mathrm{\ne }ij\; \backslash ne\; i$;
• The only element in $sun(A_{1\dots N}^{\mathrm{\prime }},N)sun\backslash left(A\text{'}\_\{1\backslash dots\; N\},\; N\backslash right)$ is a multiple of $235813235\; 813$.

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

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

• $i=1A_1^{\mathrm{\prime }}=30\to A_{1\dots 5}^{\mathrm{\prime }}=[30,1,0,7,2]\to sun([30,1,0,7,2],5)=[0]i\; =\; 1\; ~~\; A\text{'}\_1\; =\; 30\; \backslash rightarrow\; A\text{'}\_\{1\backslash dots5\}\; =\; [30,\; 1,\; 0,\; 7,\; 2]\; \backslash 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=5A_1^{\mathrm{\prime }}=28\to A_{1\dots 5}^{\mathrm{\prime }}=[4,1,0,7,28]\to sun([4,1,0,7,28],5)=[0]i\; =\; 5\; ~~\; A\text{'}\_1\; =\; 28\; \backslash rightarrow\; A\text{'}\_\{1\backslash dots5\}\; =\; [4,\; 1,\; 0,\; 7,\; 28]\; \backslash rightarrow\; sun([4,\; 1,\; 0,\; 7,\; 28],\; 5)\; =\; [0]$

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

입력

Input begins with a line containing an integer: $NN$ ($1\le N\le 1000001\; \backslash le\; N\; \backslash le\; 100\; 000$) representing the number of integers in $AA$. The next line contains $NN$ integers: $A_{i}A\_i$ ($-100000\le A_i\le 100000-100\; 000\; \backslash le\; A\_i\; \backslash 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}A\_\{1\backslash dots\; N\}$ .

5
4 1 0 7 2

3

4
10 20 30 -40

4

2
100 100

0