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:
Swap two adjacent elements. That is, choose any 1 \leq i \leq n-1, and swap a_i, a_{i+1}
Choose any integer 0\leq x\leq n-1, and replace a_i with a_i \texttt{ XOR } x for every 1 \leq i \leq n (notice that the array remains a permutation)
What is the minimal number of operations needed to sort the permutation?
Here XOR denotes the bitwise XOR operation.
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 a single integer — the smallest number of operations needed to sort this permutation.
Example
Example 1
In the first sample, we can sort the permutation with two operations as follows:
Swap a_1, a_2. The permutation becomes [1, 0, 3, 2, 5, 4, 7, 6].
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:
Swap a_1, a_2. The permutation becomes [0, 2, 1, 3, 4, 5, 6, 7].
Swap a_2, a_3. It will become [0, 1, 2, 3, 4, 5, 6, 7].