对于给定的不同非负整数 $$$(b_1, b_2, \dots, b_k)$$$ 序列,我们通过以下方式确定它是否良好:
- 考虑 $$$k$$$ 节点上的图表,其上写有从 $$$b_1$$$ 到 $$$b_k$$$ 的数字。
- 对于从 $$$1$$$ 到 $$$k$$$ 的每个 $$$i$$$:找到 $$$j$$$ ($$$1 \le j \le k$$$, $$$j\neq i$$$),其中 $$$(b_i \oplus b_j)$$$ 是所有此类 $$$j$$$ 中最小的,其中$$$\oplus$$$ 表示按位异或运算(https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。接下来,在图中编号为 $$$b_i$$$ 和 $$$b_j$$$ 的顶点之间绘制一条无向边。
- 当且仅当结果图形成一棵树(连接并且没有任何简单的循环)时,我们才说该序列是好的。
对于某些数字 $$$b_i$$$ 和 $$$b_j$$$,您可能会尝试在它们之间添加两次边。不过,您只需添加此边一次。
您可以在下面找到一个示例(对应第一个测试用例的图片)。
序列 $$$(0, 1, 5, 2, 6)$$$ 不好,因为我们无法从 $$$5$$$ 到达 $$$1$$$。
但是,序列 $$$(0, 1, 5, 2)$$$ 很好。
给定一个由不同非负整数组成的序列 $$$(a_1, a_2, \dots, a_n)$$$。您希望删除一些元素(可能没有)以使剩余的序列良好。实现这一目标所需的最小可能移除数量是多少?
可以证明,对于任意序列,我们可以删除一定数量的元素,至少留下$$$2$$$,这样剩下的序列就是好的。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 200,000$$$) — 序列的长度。
第二行包含 $$$n$$$ 不同的非负整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) - 序列的元素。
输出
您应该输出恰好一个整数——为了使剩余序列良好而需要删除的最小可能元素数。
示例
输入 #1
5 0 1 5 2 6
输出 #1
1
输入 #2
7 6 9 8 7 3 5 2
输出 #2
2
注意
请注意,您删除的数字不会影响判断结果序列是否良好的过程。
对于某些数字 $$$b_i$$$ 和 $$$b_j$$$,您可能会尝试在它们之间添加两次边。不过,您只需添加此边一次。