Polycarp có một mảng a gồm n số nguyên.

Anh ấy muốn chơi một trò chơi với mảng này. Trò chơi bao gồm một số di chuyển.
​Trong lần di chuyển đầu tiên, anh ta chọn bất kỳ phần tử nào và xóa nó (sau lần di chuyển đầu tiên, mảng chứa n − 1 phần tử). Đối với mỗi bước di chuyển tiếp theo, anh ta chọn bất kỳ yếu tố nào với hạn chế duy nhất: tính chẵn lẻ của nó sẽ khác với tính chẵn lẻ của phần tử bị xóa trong lần di chuyển trước. Nói cách khác, anh ta xen kẽ các chẵn lẻ (chẵn-lẻ-chẵn-lẻ-... hoặc lẻ-chẵn-lẻ-chẵn -...) của các phần tử bị loại bỏ. Polycarp dừng lại nếu anh ta không thể di chuyển.

Yêu cầu:

Nếu đó là động tác đầu tiên, anh ta chọn bất kỳ yếu tố nào và xóa nó;

Nếu đó là lần thứ hai hoặc bất kỳ động thái tiếp theo:

 +nếu phần tử bị xóa cuối cùng là số lẻ, Polycarp chọn bất kỳ phần tử chẵn nào và xóa nó;

 +nếu phần tử bị xóa cuối cùng là chẵn, Polycarp chọn bất kỳ phần tử lẻ nào và xóa nó.

Nếu sau khi di chuyển, Polycarp không thể di chuyển, trò chơi kết thúc.

Mục tiêu của Polycarp là giảm thiểu tổng số các phần tử không bị xóa của mảng sau khi kết thúc trò chơi. Nếu Polycarp có thể xóa toàn bộ mảng, thì tổng các phần tử không bị xóa là 0.

Giúp Polycarp tìm giá trị này.

Đầu vào

Dòng đầu tiên chứa một số nguyên n (1≤n≤2000) - số phần tử của a.

Dòng thứ hai của đầu vào chứa n số nguyên a1, a2, a3,... an (0≤ai≤106), trong đó ai là phần tử thứ i của a.

Đầu ra

In một số nguyên - tổng tối thiểu có thể của các phần tử không bị xóa của mảng sau khi kết thúc trò chơi.