给定一个由非负整数组成的序列 $a_1, a_2, \dots, a_n$。如果一个序列中任意两个相邻数字的二进制表示形式最多只有一位不同，则称该序列为“卓越序列”（remarkable）。你可以选择序列中的任意元素，并将它们更改为任意非负整数。请问为了使给定的序列成为卓越序列，最少需要更改多少个元素？

当比较两个不同长度数字的二进制表示时，我们在较短数字的前面补零以使其长度匹配。例如，要比较 $3_{(10)} = 11_{(2)}$ 和 $16_{(10)} = 10000_{(2)}$，我们将第一个数字前面补零，得到二进制序列 $00011$。二进制序列 $10000$ 和 $00011$ 在三个位置上不同，因此数字 $3$ 和 $16$ 在三位上不同。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 300\,000$)，表示序列的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 2^{60} - 1$)。

输出格式

输出一个整数，表示为了使序列 $a_1, a_2, \dots, a_n$ 成为卓越序列，最少需要更改的元素个数。

样例

输入格式 1

5
4 0 3 3 10

输出格式 1

2

说明

我们可以更改（例如）第三个和第四个元素，从而得到卓越序列 $[4, 0, 2, 10, 10]$。可以证明，无法通过仅更改一个数字使该序列成为卓越序列。