Fast XORting#12938

Fast XORting

You are given an integer which is a power of two and a permutation a_1, a_2, \ldots, a_n of 0,1,\ldots,n-1. In one operation you can do one of the following:

What is the minimal number of operations needed to sort the permutation?

Here XOR denotes the bitwise XOR operation.

Input

The first line of the input contains a single integer (1 \leq n \leq 2^{18}, is a power of two)  — the length of the permutation.

The second line contains integers a_1, a_2, , a_n which form a permutation of , , , n-1.

Output

Output a single integer  — the smallest number of operations needed to sort this permutation.

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Note

In the first sample, we can sort the permutation with two operations as follows:

  1. Swap a_1, a_2. The permutation becomes [1, 0, 3, 2, 5, 4, 7, 6].

  2. Choose x = 1, and XOR all elements with . It will become [0, 1, 2, 3, 4, 5, 6, 7].

In the second sample, we can sort the permutation with two operations as follows:

  1. Swap a_1, a_2. The permutation becomes [0, 2, 1, 3, 4, 5, 6, 7].

  2. Swap a_2, a_3. It will become [0, 1, 2, 3, 4, 5, 6, 7].