Protein Identification

A protein is a chain of amino acids. Its sequence can be studied with tandem mass spectrometry (MS2).

For this problem assume the following simplified setting.

• A protein is a chain of at most $400$ amino acids.
• There are only two kinds of amino acid, $P$ and $Q$.
• $P$ has mass $97.05276$ daltons and $Q$ has mass $128.05858$ daltons.

The result of an MS2 experiment is a set of real numbers; each number is called a peak. For the true protein, this set contains the mass of every prefix and every suffix of the protein (including the mass of the whole protein) and nothing else. Note that a protein and its reverse produce exactly the same set of prefix and suffix masses.

An experiment on an unknown protein is not perfect, so its result satisfies the following.

• Some prefix or suffix masses may be missing from the set.
• The set may contain peaks that are not the mass of any prefix or suffix of the protein. Such a peak is called a noise peak.
• Every peak is positive.
• The largest peak equals the mass of the whole protein.
• Every peak that does correspond to a prefix or suffix mass is exact.

Given the experimental result, consider every protein made of $P$ and $Q$ (length at most $400$) whose total mass equals the largest peak. For such a protein, a noise peak is a peak of the input that is not equal to any prefix or suffix mass of that protein. Find the minimum possible number of noise peaks.

The first line contains the number of peaks $n$ ($1 \le n \le 100000$).

Each of the next $n$ lines contains one peak $p_i$.

The input always satisfies all of the conditions above, and all peaks are distinct. Each peak is given with at most $5$ digits after the decimal point.

Print a single integer: the minimum possible number of noise peaks over all proteins made of $P$ and $Q$ (length at most $400$) whose total mass equals the largest peak.