Problem Description

In a poet’s eyes, numbers are the rhythm of life and a way to express poetry.

Xiao Lan, a top modern poet and mathematician, is known as the “mathematical poet”. He is good at blending cold numbers with abstract poetic meaning, and presenting the beauty of mathematics on paper with elegant words.

One day, Xiao Lan sits quietly at his desk. In front of him are $n$ numbers, in order: $a_1, a_2, \cdots, a_n$, shining brightly. Xiao Lan realizes that if a number can be written as the sum of several (at least two) consecutive positive integers, then it contains poetic meaning. For example, the number $6$ contains poetic meaning because it can be written as $1 + 2 + 3$. But $8$ lacks poetic meaning because it cannot be expressed as a sum of consecutive positive integers.

Xiao Lan wants all the numbers in front of him to contain poetic meaning, so he decides to delete some of these $n$ numbers. How many numbers does Xiao Lan need to delete so that all remaining numbers contain poetic meaning?

Input Format

The first line contains an integer $n$, representing the number of displayed numbers.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$, separated by a single space, representing the displayed numbers.

Output Format

Output a single line containing an integer, representing the number of numbers Xiao Lan needs to delete so that all remaining numbers contain poetic meaning.

3
3 6 8

1

Hint

Sample Explanation

In the sample, the number $3$ can be written as $1 + 2$, and the number $6$ can be written as $1 + 2 + 3$. The number $8$ cannot be written as a sum of consecutive positive integers, so the number of deleted numbers is $1$.

Constraints

For $30\%$ of the testdata, $1 \le n \le 10^3$, $1 \le a_i \le 10^3$.
For all testdata, $1 \le n \le 2 \times 10^5$, $1 \le a_i \le 10^{16}$.

Translated by ChatGPT 5