Cao Bằng tôi yêu

3M sắp tới có kì thi giữa kì. Bố của cậu hứa rằng nếu cậu đạt điểm cao trong kì thi
giữa kì môn Mỹ thuật, ông sẽ thưởng cho cậu một chuyến đi Cao Bằng, nơi có những
người bạn rất dễ thương của cậu. Để đạt điểm cao, 3M cần tô màu một bức tranh thật
đẹp. Tuy nhiên, thầy giáo Mỹ thuật là người rất kỹ tính, thầy quy định rằng một bức
tranh đẹp là bức tranh mà tất cả các màu sắc trong đó phải có cùng tính chẵn lẻ.

Hiện tại, bức tranh của 3M bao gồm \(N\) mảng màu, mỗi mảng màu được biểu diễn bằng
một số nguyên dương \(a_1, a_2, \ldots, a_N\). Để đạt được yêu cầu của thầy giáo, cậu có
thể thực hiện thao tác pha màu như sau --- cậu chọn hai mảng màu ở vị trí \(i\) và \(j\)
có tính chẵn lẻ khác nhau:

• Nếu \(a_i < a_j\), màu \(a_i\) sẽ được thay thế bằng giá trị \(a_i + a_j\). Màu \(a_j\) vẫn giữ nguyên.

Hãy giúp 3M tính xem cần thực hiện ít nhất bao nhiêu thao tác để cậu có thể thăm những
người bạn của cậu.

Input

Vào từ file văn bản CCB.INP:

• Dòng đầu chứa số nguyên dương \(N\) (\(1 \le N \le 2 \times 10^{5}\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \ldots, a_N\) (\(1 \le a_i \le 10^{9}\)).

Output

Ghi ra file văn bản CCB.OUT:

• In ra số thao tác tối thiểu mà 3M cần để đạt điểm cao.

Example

3
2 3 4

2

4
1 1 1 3

0

Scoring

• \(40\%\) số test tương ứng với \(40\%\) số điểm có \(n \le 2000\).
• \(20\%\) số test tương ứng với \(20\%\) số điểm có các màu trong các mảng màu ban đầu cùng chẵn hoặc cùng lẻ.
• \(40\%\) số test còn lại tương ứng với \(40\%\) số điểm của bài không có ràng buộc gì thêm.