CSES - KILO 2018 4/5 - Interview
  • 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