Limits 1s, 512 MB

Ridoy is a world class programmer. He writes his programs with a lot of care so that the odds of a bug being showed up is as little as possible.

You are giving an interview to join Ridoy's company. Your interviewer asks you to solve the problem of minimizing the odds. But the problem is much easier than what Ridoy has to deal with.

Formally, you will be given an array of N integers. You will be able to perform just one operation in the array. The operation can be broken down in following steps:

  1. Pick two indexes i and j, ( 0 ≤ i < j ≤ S - 1 ). Here, S is the current size of the array.

  2. Add the value of index i and j together and insert the sum to the end of the array.

  3. Delete the value of index i and index j from the array.

You can perform the above operation as many times as you want. You have to minimize the number of odd numbers that remain in the array after these operations.

Input

The first line of input is an integer N (≤ 100000), the number of elements in the initial array. Then follow N positive numbers, each within 1 to 1018.

Output

Output a single number, the minimum number of odd numbers that will remain after the end of all operations.

Sample

InputOutput
2
4 5
1

Odd number is an integer number that is not divisible by 2.

Submit

Login to submit.

Statistics

91% Solution Ratio
tutul_hossainEarliest, May '19
skmonirFastest, 0.0s
tutul_hossainLightest, 131 kB
mdvirusShortest, 172B
Toph uses cookies. By continuing you agree to our Cookie Policy.