Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Minimize the Odds

By TarifEzaz · 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.

    Discussion

    Statistics


    95% Solution Ratio

    tutul_hossainEarliest, 11M ago

    skmonirFastest, 0.0s

    tutul_hossainLightest, 131 kB

    mdvirusShortest, 172B

    Submit

    Login to submit

    Editorial

    Count the number of odd numbers in the array. You will be able to figure out the result from there. Read more...

    Related Contests

    Stamford University Bangladesh Summer Contest 2019 Ended at 2019-05-03 07:00:00 +0000 UTC
    Replay of Stamford University Bangladesh Summer Contest 2019 Ended at 2019-05-03 18:00:00 +0000 UTC