给定一个整数 $n$（$n$ 是 2 的幂）和一个 $0, 1, \dots, n-1$ 的排列 $a_1, a_2, \dots, a_n$。在一次操作中，你可以执行以下任一操作：

• 交换两个相邻元素。即选择任意 $1 \le i \le n-1$，并交换 $a_i, a_{i+1}$。
• 选择任意整数 $0 \le x \le n-1$，并将每个 $a_i$ 替换为 $a_i \oplus x$（注意，数组在操作后仍为一个排列）。

将该排列排序所需的最少操作次数是多少？

这里 $\oplus$ 表示按位异或运算。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 2^{18}$，$n$ 是 2 的幂）—— 排列的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，它们构成了 $0, 1, \dots, n-1$ 的一个排列。

输出格式

输出一个整数 —— 将该排列排序所需的最少操作次数。

样例

样例输入 1

8
0 1 3 2 5 4 7 6

样例输出 1

2

样例输入 2

8
2 0 1 3 4 5 6 7

样例输出 2

2

说明

在第一个样例中，我们可以通过以下两次操作将排列排序：

1. 交换 $a_1, a_2$。排列变为 $[1, 0, 3, 2, 5, 4, 7, 6]$。
2. 选择 $x = 1$，并将所有元素与 $1$ 进行异或。排列变为 $[0, 1, 2, 3, 4, 5, 6, 7]$。

在第二个样例中，我们可以通过以下两次操作将排列排序：

1. 交换 $a_1, a_2$。排列变为 $[0, 2, 1, 3, 4, 5, 6, 7]$。
2. 交换 $a_2, a_3$。排列变为 $[0, 1, 2, 3, 4, 5, 6, 7]$。