- Time limit: 1.00 s
- Memory limit: 128 MB
You are in a job interview, and you are given a task about binary trees. You have a perfect binary tree of height h. The tree has 2^h leaves each containing a value. What is the minimum number of inversions required to sort the values of the leaves?
One inversion swaps the left and the right subtree of a chosen node in the tree. For clarification, see the example.
Input
The first line contains a single integer h, the height of the tree. The second line contains 2^h space separated integers, a_1, a_2, \ldots, a_{2^h} the values of the leaves.
Output
Output the minimum number of inversions required to sort the values of leaves. If it's impossible to sort the values of leaves, output QAQ
.
Constraints
- 0 \le h \le 17
- 1 \le a_i \le 10^9
Examples
Input:
3 5 6 6 7 2 1 4 5
Output:
2
Initially the tree looks like this:
After doing an inversion for the root, the tree looks like this:
After that, one more inversion is required to sort the tree:
Input:
2 1000 100 10 1
Output:
3
Input:
2 1 4 2 3
Output:
QAQ