CF1446C.Xor Tree

For a given sequence of distinct non-negative integers $(b_1, b_2, \dots, b_k)$ we determine if it is good in the following way:

• Consider a graph on $k$ nodes, with numbers from $b_1$ to $b_k$ written on them.
• For every $i$ from $1$ to $k$ : find such $j$ ( $1 \le j \le k$ , $j\neq i$ ), for which $(b_i \oplus b_j)$ is the smallest among all such $j$ , where $\oplus$ denotes the operation of bitwise XOR (https://en.wikipedia.org/wiki/Bitwise_operation#XOR). Next, draw an undirected edge between vertices with numbers $b_i$ and $b_j$ in this graph.
• We say that the sequence is good if and only if the resulting graph forms a tree (is connected and doesn't have any simple cycles).

It is possible that for some numbers $b_i$ and $b_j$ , you will try to add the edge between them twice. Nevertheless, you will add this edge only once.

You can find an example below (the picture corresponding to the first test case).

Sequence $(0, 1, 5, 2, 6)$ is not good as we cannot reach $1$ from $5$ .

However, sequence $(0, 1, 5, 2)$ is good.

You are given a sequence $(a_1, a_2, \dots, a_n)$ of distinct non-negative integers. You would like to remove some of the elements (possibly none) to make the remaining sequence good. What is the minimum possible number of removals required to achieve this goal?

It can be shown that for any sequence, we can remove some number of elements, leaving at least $2$ , so that the remaining sequence is good.
对于给定的由不同的非负整数组成的序列 $(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$ 表示位XOR操作(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$ ，这样剩下的序列就是好的。

The first line contains a single integer $n$ ( $2 \le n \le 200,000$ ) — length of the sequence.

The second line contains $n$ distinct non-negative integers $a_1, a_2, \ldots, a_n$ ( $0 \le a_i \le 10^9$ ) — the elements of the sequence.
输入

第一行包含一个整数 $n$ ( $2 \le n \le 200,000$ ) - 序列长度。

第二行包含 $n$ 个不同的非负整数 $a_1, a_2, \ldots, a_n$ ( $0 \le a_i \le 10^9$ ) - 序列的元素。

You should output exactly one integer — the minimum possible number of elements to remove in order to make the remaining sequence good.
输出

您应该输出一个整数--为使剩余序列良好而需要移除的元素的最小数目。

Note that numbers which you remove don't impact the procedure of telling whether the resulting sequence is good.

It is possible that for some numbers $b_i$ and $b_j$ , you will try to add the edge between them twice. Nevertheless, you will add this edge only once.
备注

请注意，删除的数字不会影响判断序列是否正确的程序。

对于某些数字 $b_i$ 和 $b_j$ ，您可能会尝试添加两次它们之间的边。然而，您只需添加一次。