#1958 · Trừ đi phần giao

Trong một thế giới nơi mỗi số nguyên là một dạng năng lượng, bạn đang nắm giữ một dãy năng lượng gồm N phần tử. Mỗi phần tử mang một giá trị năng lượng nguyên dương.

Bạn có thể thực hiện một thao tác đặc biệt bao nhiêu lần tùy thích. Mỗi lần, bạn chọn hai phần tử khác nhau trong dãy (tức là chọn hai chỉ số $i < j$), rồi lấy phép AND bit của hai phần tử này và trừ nó đi khỏi một trong hai phần tử.

Cụ thể, nếu chọn A[i] và A[j], thì bạn có thể tính A[i] & A[j] (phép AND bit) và sau đó trừ kết quả này khỏi A[i] hoặc A[j].

Mục tiêu của bạn là: biến càng nhiều phần tử về 0 càng tốt bằng các thao tác trên.

Hãy tính số lượng phần tử lớn nhất mà bạn có thể đưa về 0.

• Dòng đầu tiên chứa số nguyên N — số lượng phần tử trong dãy.
• Dòng thứ hai chứa N số nguyên A₁, A₂, ..., Aₙ — giá trị năng lượng ban đầu của từng phần tử.

In ra một số nguyên: số lượng phần tử tối đa có thể biến thành 0 sau khi thực hiện các thao tác.