Practice on Toph

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

Limits 1s, 512 MB

Today is Anik's Birthday. Saad wants to give Anik an array as birthday present.

But Anik is afraid of Odd numbers.He will get scared if the G.C.D of all the numbers of the array is an odd number.

So Saad wants to remove minimum possible numbers so that The G.C.D of all the numbers of the array becomes even number. And you are ( As always) the only one who can help Saad.

If it is impossible to make the G.C.D an even number print -1.

G.C.D(Greatest Common Divisor) of some numbers means the greatest number that can divide the given numbers.

Input

In the first line, There will be an integer N, (the size of the array)

In the next line N numbers will be given.

(1 <= N <= 100000)
(1 <= Given Numbers <= 1000000)

Output

Print the minimum possible numbers as described in the statement if it is possible to make the G.C.D an even number. If it is not possible, then print -1.

Samples

InputOutput
2
1 2
1
InputOutput
5
1 1 2 4 2
2

Statistics

81% Solution Ratio

dip_BRUREarliest, May '19

abu_fayeemFastest, 0.0s

dip_BRURLightest, 131 kB

bokaifShortest, 90B

Submit

 CSE Fest 2019 Intra BUET Junior Programming Contest Jan '19 