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)$，我们按如下方式判断它是否为“好序列”（good）：

• 构造一个包含 $k$ 个节点的图，各节点上分别标有数字 $b_1$ 到 $b_k$；
• 对每个 $i$（$1 \le i \le k$）：找出满足 $1 \le j \le k$ 且 $j \ne i$ 的下标 $j$，使得 $(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$ 个，且构成好序列。

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$，你可能会尝试两次添加它们之间的边；但该边仅会被添加一次。