Winning First Moves in Divisor Stone Game

Bessie and Elsie are playing a stone‐removal game using N piles of stones. For each 1 ≤ i ≤ N, pile i contains a_i stones. The rules of the game are as follows:

• Bessie (the first player) chooses a positive integer \(s_1\) and removes \(s_1\) stones from any pile that has at least \(s_1\) stones.
• Then Elsie chooses a positive integer \(s_2\) such that \(s_1\) divides \(s_2\) (i.e. \(s_1 \mid s_2\)) and removes \(s_2\) stones from any pile that has at least \(s_2\) stones.
• Next, Bessie chooses \(s_3\) satisfying \(s_2 \mid s_3\) and removes \(s_3\) stones from some pile with at least \(s_3\) stones, and so on.
• In general, if \(s_i\) is the number of stones removed in move \(i\), then the next move must remove \(s_{i+1}\) stones with \(s_i \mid s_{i+1}\).

The first player who is unable to make a valid move loses.

Bessie wants to guarantee a win. She can secure her victory immediately if her first move leaves no valid move for Elsie. Notice that on Elsie’s turn the minimum stone removal is \(s_1\) (since \(s_1 \mid s_2\) implies \(s_2 \ge s_1\)). Thus, if after Bessie’s move every pile has strictly fewer than \(s_1\) stones, Elsie cannot move and Bessie wins immediately.

More precisely, suppose Bessie removes \(s_1\) stones from pile \(i\). After her move, pile \(i\) will have \(a_i - s_1\) stones and every other pile \(j \ne i\) remains unchanged with \(a_j\) stones. In order for Elsie to have no move, the following must hold:

[ \begin{aligned} a_i - s_1 &< s_1 &\quad &\text{(for the pile chosen by Bessie)}\ a_j &< s_1 &\quad &\text{(for every other pile)} \end{aligned} ]

This immediately implies that:

• For the chosen pile: \(a_i < 2s_1\) (together with \(s_1 \le a_i\) because the move must be legal),
• For every other pile: \(a_j < s_1\).

We define \(T_i\) as the maximum stone count among all piles except pile \(i\). (In the case where N = 1, define \(T_i = 0\).)

Then, a first move is immediately winning if and only if Bessie picks a pile \(i\) and a positive integer \(s_1\) such that:

[ \begin{aligned} s_1 &\le a_i,\ a_i &< 2s_1,\ s_1 &> T_i. \end{aligned} ]

Rewriting \(a_i \frac{a_i}{2}\). Therefore, for a fixed pile \(i\) the valid choices for \(s_1\) are all integers in the interval

[ \Big[\max\Big(T_i+1, \Big\lfloor\frac{a_i}{2}\Big\rfloor+1\Big),; a_i\Big]. ]

Two first moves are considered different if either the chosen pile or the number of stones removed are different. Your task is to compute the number of first‐move choices for which Bessie has a winning strategy.

Input Format

The input begins with a line containing a single integer N (1 ≤ N ≤ 10⁵). The next line contains N space‐separated integers, where the i^th integer is a_i (1 ≤ a_i ≤ 10⁶).

Output Format

Output a single integer representing the number of winning first moves Bessie can use.

inputFormat

Input begins with an integer N on a single line. The next line contains N integers a₁, a₂, ..., a_N separated by spaces.

outputFormat

Output a single integer that is the total number of winning first moves available to Bessie.

sample

7
7

4