Dịp tết vừa qua, Do có nhiều cố gắng trong học tập và đạt được kết quả tốt trong học kỳ I, HT được gia đình cho đi tham quan nhiều địa điểm du lịch. Trong số những địa điểm du lịch đã đi qua thì HT đặc biệt chú ý một địa điểm của khu du lịch ABC. Đặc điểm của khu du lịch đó là một bên đường có dãy đồi cát rất đẹp, một bên đường còn lại là dãy các gian hàng dịch vụ, mỗi một gian hàng dịch vụ này có các trò tiêu khiển hay phục vụ rất nhiều món ăn ngon. Các gian hàng dịch vụ được đánh số lần lượt từ 1 đến ~ n ~ dọc theo con đường, gian hàng thứ ~ i ~ có mức độ yêu thích có giá trị ~ a_i ~ ~ (i = 1,2,…n) ~. HT muốn vào các gian hàng dịch vụ này để tham quan nhưng không có nhiều thời gian nên HT đã chọn ra các gian hàng thỏa mãn tất cả các tiêu chí sau: + Dãy các gian hàng dịch vụ được chọn phải có mức độ yêu thích tăng dần (không bằng). + Tất cả các gian hàng được chọn phải có giá trị yêu thích chia hết cho 2. + Nhiều gian hàng dịch vụ nhất có thể được.

Yêu cầu: Bạn hãy giúp HT chọn được nhiều gian hàng dịch vụ để tham quan nhất thỏa mãn tất cả các yêu cầu trên.

Dữ liệu vào

• Dòng đầu chứa số nguyên dương ~ n ~ ~ ( n ≤ 5000) ~
• Trong ~ n ~ dòng tiếp theo, dòng thứ ~ i ~ chứa số nguyên dương ~ a_i ~ ~ (i = 1,2,…n; |a_i| ≤ 10^9) ~.

Kết quả

• Ghi số lượng gian hàng dịch vụ nhiều nhất mà HT được chọn thỏa mãn tất cả các yêu cầu.

Ví dụ:

Input 1

6
3
2
6
6
8
9 

Output 1

3