Cây XOR

Cho một dãy gồm $k$ số nguyên không âm đôi một phân biệt $(b_1,b_2,\dots ,b_k)$. Ta xây dựng một đồ thị vô hướng $k$ đỉnh, đỉnh thứ $i$ mang giá trị $b_i$, theo quy tắc sau:

• Với mỗi $i$ từ $1$ đến $k$, tìm chỉ số $j$ ($j\ne i$) sao cho giá trị $b_i\oplus b_j$ là nhỏ nhất trong tất cả các lựa chọn của $j$ (ở đây $\oplus$ là phép XOR theo bit). Thêm một cạnh vô hướng nối đỉnh $b_i$ và đỉnh $b_j$.

Nếu một cạnh bị thêm hai lần thì nó chỉ được tính một lần. Dãy được gọi là tốt nếu và chỉ nếu đồ thị thu được là một cây (liên thông và không có chu trình đơn).

Cho dãy $(a_1,a_2,\dots ,a_n)$ gồm $n$ số nguyên không âm đôi một phân biệt. Bạn được phép xoá đi một số phần tử (có thể không xoá phần tử nào) để dãy còn lại trở thành dãy tốt. Hãy tìm số phần tử ít nhất cần xoá.

Có thể chứng minh rằng với mọi dãy, luôn tồn tại cách xoá để dãy còn lại có ít nhất $2$ phần tử và là dãy tốt.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — độ dài của dãy.
• Dòng thứ hai chứa $n$ số nguyên phân biệt $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

• In ra một số nguyên duy nhất — số phần tử ít nhất cần xoá để dãy còn lại là dãy tốt.

Ràng buộc

• $2\le n\le 200000$
• $0\le a_i\le {10}^9$
• Các $a_i$ đôi một phân biệt.

Ví dụ