Một mảng được gọi là đẹp nếu như tất các các phần tử trong mảng đều là số lẻ hoặc đều là số chẵn.

Với mỗi thao tác thì bạn có thể xóa đi một phần tử trong mảng. Hãy tìm số thao tác ít nhất để chuyển mảng thành một mảng đẹp.

Input

• Dòng đầu chứa số nguyên ~n~ ~(1 \le n \le 10^4)~
• Dòng thứ 2 là mảng gồm ~n~ phần tử ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^7)~

Output

• Số thao tác ít nhất để chuyển mảng thành một mảng đẹp.

Example

Input 1:

5
1 2 3 4 5

Output 1:

2

Giải thích:

• Ta sẽ xoá số 2 và 4 để mảng chỉ toàn số lẻ

Input 2:

4
2 4 6 8

Output 2:

0

Giải thích:

• Mảng đã đẹp không cần xoá số nào