← 返回题目列表

Codeforces · 1446/C

C. 异或树

中文机器翻译题面 查看原题

对于给定的不同非负整数 $$$(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$$$,您可能会尝试在它们之间添加两次边。不过,您只需添加此边一次。