달과 해

정수로 이루어진 비어 있지 않은 수열 $S$와 양의 정수 $K$가 있다. 함수 $moon()$과 $sun()$은 다음과 같이 정의된다.

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

예를 들어,

• $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\left(S_{1\dots |S|}, |S|\right)$는 항상 원소가 정확히 하나인 수열이다.

$N$개의 정수로 이루어진 수열 $A_{1\dots N}$이 주어진다. 인덱스 $i = [1\dots N]$가 hot이라는 것은 다음 조건을 만족하는 수열 $A'_{1\dots N}$이 존재한다는 것이다.

• $A'_i \ne A_i$이고 $A_i'$는 $-100\,000$ 이상 $100\,000$ 이하의 정수이다.
• 모든 $j \ne i$에 대해 $A'_j = A_j$이다.
• $sun\left(A'_{1\dots N}, N\right)$의 유일한 원소가 $235\,813$의 배수이다.

이 문제에서 할 일은 주어진 $A_{1\dots N}$에서 hot인 인덱스의 개수를 세는 것이다.

예를 들어 $A_{1\dots 5} = [4, 1, 0, 7, 2]$에는 hot인 인덱스가 $3$개 있으며, 이는 $\{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'_3 = -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'_5 = 28 \rightarrow A'_{1\dots5} = [4, 1, 0, 7, 28] \rightarrow sun([4, 1, 0, 7, 28], 5) = [0]$

$0$과 $-471\,626$은 모두 $235\,813$의 배수이다. 반면 인덱스 $i = 2$는 hot이 아니다. $-100\,000$ 이상 $100\,000$ 이하의 정수 $A'_2 \ne A_2$ 중에서 $sun(A'_{1\dots 5}, 5)$의 유일한 원소가 $235\,813$의 배수가 되게 하는 값이 없기 때문이다. 인덱스 $i = 4$도 같은 이유로 hot이 아니다.

첫 줄에 정수 $N$ ($1 \le N \le 100\,000$)이 주어진다. 이는 $A$에 들어 있는 정수의 개수이다. 다음 줄에 $N$개의 정수 $A_i$ ($-100\,000 \le A_i \le 100\,000$)가 주어진다. 이는 정수 수열 $A$이다.

주어진 $A_{1\dots N}$에서 hot인 인덱스의 개수를 한 줄에 출력한다.