You are very angry at Victor because of his problems with weird statements and subtasks with no real links between them, so you have decided to take revenge. That is, you will break into his house and detune his piano.

Victor's piano is very large and has n ≤ 10⁵ strings, which are all originally tuned to a given integer frequency. You know from music theory that the most important interval in music is the octave, that is, two notes such that the frequency of one of them is the double of the frequency of the other. As a consequence, in order to break the harmony of the piano, you wish to alter the frequencies of some strings such that in the end, there is no pair (i,j) of strings such that the frequency of string i is exactly twice that of string j.

In order to change the strings' frequencies, you own two tuning keys. The first one, called Nimbus440, is very handy and allows you to tune a string to any positive integer frequency in one move (the strings are very strong and can be tuned to arbitrary large frequencies). The second one, called XorOne, is much less useful, and only allows you to increase an even frequency by one, or decrees an odd frequency by one (for example, it can change 4 into 5, or 5 into 4, but not 4 into 3 or 3 into 4). Why do you even have it?

When leaving home to go commit the crime, you were distracted and took one of the two keys at random. Thus you cannot choose which key you'll use. Furthermore, you would like to finish quickly in order not to get caught, so you would like to detune the piano in a minimum number of key uses. Your task is to find this minimum.

Input:
4
2 2 4 4
Nimbus440

Output:
2

Input:
2
7 2
Nimbus440

Output:
0

Input:
4
2 4 6 10
XorOne

Output:
2