CF414C.Mashmokh and Reverse Operation

Mashmokh's boss, Bimokh, didn't like Mashmokh. So he fired him. Mashmokh decided to go to university and participate in ACM instead of finding a new job. He wants to become a member of Bamokh's team. In order to join he was given some programming tasks and one week to solve them. Mashmokh is not a very experienced programmer. Actually he is not a programmer at all. So he wasn't able to solve them. That's why he asked you to help him with these tasks. One of these tasks is the following.

You have an array a of length 2_n_ and m queries on it. The i-th query is described by an integer q__i. In order to perform the i-th query you must:

• split the array into 2_n_ - q__i parts, where each part is a subarray consisting of 2_q__i_ numbers; the j-th subarray (1 ≤ j ≤ 2_n_ - q__i) should contain the elements a[(j - 1)·2_q__i_ + 1], a[(j - 1)·2_q__i_ + 2], ..., a[(j - 1)·2_q__i_ + 2_q__i_];
• reverse each of the subarrays;
• join them into a single array in the same order (this array becomes new array a);
• output the number of inversions in the new a.

Given initial array a and all the queries. Answer all the queries. Please, note that the changes from some query is saved for further queries.

马什莫赫的老板比莫赫不喜欢马什莫赫，因此解雇了他。马什莫赫决定去上大学并参加 ACM 竞赛，而不是另找一份工作。他希望成为比莫赫团队的一员。为了加入该团队，他被布置了一些编程任务，并有一周时间来解决它们。马什莫赫并不是一位经验丰富的程序员——事实上，他根本就不是程序员。因此他无法独立完成这些任务。这正是他请你帮忙的原因。其中一道任务如下：

你有一个长度为 $2^n$ 的数组 $a$，以及 $m$ 个关于该数组的查询。第 $i$ 个查询由一个整数 $q_i$ 描述。为执行第 $i$ 个查询，你必须：

• 将数组划分为 $2^{n - q_i}$ 个部分，其中每个部分是一个包含 $2^{q_i}$ 个数的子数组；第 $j$ 个子数组（$1 \le j \le 2^{n - q_i}$）应包含元素
  $a[(j - 1)\cdot 2^{q_i} + 1],\ a[(j - 1)\cdot 2^{q_i} + 2],\ \dots,\ a[(j - 1)\cdot 2^{q_i} + 2^{q_i}]$；
• 将每个子数组进行翻转；
• 按照原来的顺序将这些子数组连接成一个单一数组（该数组成为新的数组 $a$）；
• 输出新数组 $a$ 中的逆序对数量。

给定初始数组 $a$ 以及所有查询，请回答全部查询。请注意：某次查询所引起的数组变化将保留至后续查询中。

The first line of input contains a single integer n (0 ≤ n ≤ 20).

The second line of input contains 2_n_ space-separated integers a[1], a[2], ..., a[2_n_] (1 ≤ a[i] ≤ 109), the initial array.

The third line of input contains a single integer m (1 ≤ m ≤ 106).

The fourth line of input contains m space-separated integers _q_1, _q_2, ..., q__m (0 ≤ q__i ≤ n), the queries.

Note: since the size of the input and output could be very large, don't use slow output techniques in your language. For example, do not use input and output streams (cin, cout) in C++.

输入的第一行包含一个整数 $n$（$0 \leq n \leq 20$）。

输入的第二行包含 $2^n$ 个用空格分隔的整数 $a[1],\,a[2],\,\dots,\,a[2^n]$（$1 \leq a[i] \leq 10^9$），表示初始数组。

输入的第三行包含一个整数 $m$（$1 \leq m \leq 10^6$）。

输入的第四行包含 $m$ 个用空格分隔的整数 $q_1,\,q_2,\,\dots,\,q_m$（$0 \leq q_i \leq n$），表示查询。

注意：由于输入和输出的数据量可能非常大，请勿在你的编程语言中使用低效的输入输出方式。例如，在 C++ 中请不要使用输入输出流（cin、cout）。

Output m lines. In the i-th line print the answer (the number of inversions) for the i-th query.

输出 m 行。在第 i 行中，输出第 i 个查询的答案（即逆序对的数量）。

If we reverse an array x[1], x[2], ..., x[n] it becomes new array y[1], y[2], ..., y[n], where y[i] = x[n - i + 1] for each i.

The number of inversions of an array x[1], x[2], ..., x[n] is the number of pairs of indices i, j such that: i < j and x[i] > x[j].

如果我们反转数组 $x[1],\,x[2],\,\dots,\,x[n]$，它将变为新数组 $y[1],\,y[2],\,\dots,\,y[n]$，其中对每个 $i$，都有 $y[i] = x[n - i + 1]$。

数组 $x[1],\,x[2],\,\dots,\,x[n]$ 的逆序对数是指满足如下条件的下标对 $(i,\,j)$ 的个数：$i < j$ 且 $x[i] > x[j]$。