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 2n and m queries on it. The i-th query is described by an integer qi. In order to perform the i-th query you must:

  * split the array into 2n - qi parts, where each part is a subarray consisting of 2qi numbers; the j-th subarray (1 ≤ j ≤ 2n - qi) should contain the elements a[(j - 1)·2qi + 1], a[(j - 1)·2qi + 2], ..., a[(j - 1)·2qi + 2qi]; 
  * 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.

Input

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

The second line of input contains 2n space-separated integers a[1], a[2], ..., a[2n] (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 q1, q2, ..., qm (0 ≤ qi ≤ 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++.

Output

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

Examples

Input

2
2 1 4 3
4
1 2 0 2


Output

0
6
6
0


Input

1
1 2
3
0 1 1


Output

0
1
0

Note

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].
2
1 1 3 1
3
0 1 2

                                                               1
                                                               0
                                                               3

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
template <class T>
inline void RST(T &A) {
  memset(A, 0, sizeof(A));
}
template <class T>
inline void FLC(T &A, int x) {
  memset(A, x, sizeof(A));
}
template <class T>
inline void CLR(T &A) {
  A.clear();
}
const int dx4[] = {-1, 0, 1, 0};
const int dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dy8[] = {0, 1, 0, -1, -1, 1, -1, 1};
const int dxhorse[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dyhorse[] = {1, -1, 2, -2, 2, -2, 1, -1};
const int mod = 1000000007;
const int inf = 0x3f3f3f3f;
const long long inff = 1LL << 60;
const double eps = 1e-9;
const double oo = 1e25;
const double pi = acos(-1.0);
template <class T>
inline void checkMin(T &a, const T b) {
  if (b < a) a = b;
}
template <class T>
inline void checkMax(T &a, const T b) {
  if (a < b) a = b;
}
template <class T>
inline void checkMin(T &a, T &b, const T x) {
  checkMin(a, x), checkMin(b, x);
}
template <class T>
inline void checkMax(T &a, T &b, const T x) {
  checkMax(a, x), checkMax(b, x);
}
template <class T, class C>
inline void checkMin(T &a, const T b, C c) {
  if (c(b, a)) a = b;
}
template <class T, class C>
inline void checkMax(T &a, const T b, C c) {
  if (c(a, b)) a = b;
}
template <class T>
inline T min(T a, T b, T c) {
  return min(min(a, b), c);
}
template <class T>
inline T max(T a, T b, T c) {
  return max(max(a, b), c);
}
template <class T>
inline T min(T a, T b, T c, T d) {
  return min(min(a, b), min(c, d));
}
template <class T>
inline T max(T a, T b, T c, T d) {
  return max(max(a, b), max(c, d));
}
template <class T>
inline T sqr(T a) {
  return a * a;
}
template <class T>
inline T cub(T a) {
  return a * a * a;
}
template <class T>
inline T ceil(T x, T y) {
  return (x - 1) / y + 1;
}
inline int sgn(double x) { return x < -eps ? -1 : x > eps; }
inline int sgn(double x, double y) { return sgn(x - y); }
inline double cot(double x) { return 1. / tan(x); };
inline double sec(double x) { return 1. / cos(x); };
inline double csc(double x) { return 1. / sin(x); };
namespace BO {
inline bool _1(int x, int i) { return bool(x & 1 << i); }
inline bool _1(long long x, int i) { return bool(x & 1LL << i); }
inline long long _1(int i) { return 1LL << i; }
inline long long _U(int i) { return _1(i) - 1; };
inline int reverse_bits(int x) {
  x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa);
  x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc);
  x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0);
  x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00);
  x = ((x >> 16) & 0x0000ffff) | ((x << 16) & 0xffff0000);
  return x;
}
inline long long reverse_bits(long long x) {
  x = ((x >> 1) & 0x5555555555555555LL) | ((x << 1) & 0xaaaaaaaaaaaaaaaaLL);
  x = ((x >> 2) & 0x3333333333333333LL) | ((x << 2) & 0xccccccccccccccccLL);
  x = ((x >> 4) & 0x0f0f0f0f0f0f0f0fLL) | ((x << 4) & 0xf0f0f0f0f0f0f0f0LL);
  x = ((x >> 8) & 0x00ff00ff00ff00ffLL) | ((x << 8) & 0xff00ff00ff00ff00LL);
  x = ((x >> 16) & 0x0000ffff0000ffffLL) | ((x << 16) & 0xffff0000ffff0000LL);
  x = ((x >> 32) & 0x00000000ffffffffLL) | ((x << 32) & 0xffffffff00000000LL);
  return x;
}
template <class T>
inline bool odd(T x) {
  return x & 1;
}
template <class T>
inline bool even(T x) {
  return !odd(x);
}
template <class T>
inline T low_bit(T x) {
  return x & -x;
}
template <class T>
inline T high_bit(T x) {
  T p = low_bit(x);
  while (p != x) x -= p, p = low_bit(x);
  return p;
}
template <class T>
inline T cover_bit(T x) {
  T p = 1;
  while (p < x) p <<= 1;
  return p;
}
template <class T>
inline int cover_idx(T x) {
  int p = 0;
  while (_1(p) < x) ++p;
  return p;
}
inline int clz(int x) { return __builtin_clz(x); }
inline int clz(long long x) { return __builtin_clzll(x); }
inline int ctz(int x) { return __builtin_ctz(x); }
inline int ctz(long long x) { return __builtin_ctzll(x); }
inline int lg2(int x) { return !x ? -1 : 31 - clz(x); }
inline int lg2(long long x) { return !x ? -1 : 63 - clz(x); }
inline int low_idx(int x) { return !x ? -1 : ctz(x); }
inline int low_idx(long long x) { return !x ? -1 : ctz(x); }
inline int high_idx(int x) { return lg2(x); }
inline int high_idx(long long x) { return lg2(x); }
inline int parity(int x) { return __builtin_parity(x); }
inline int parity(long long x) { return __builtin_parityll(x); }
inline int count_bits(int x) { return __builtin_popcount(x); }
inline int count_bits(long long x) { return __builtin_popcountll(x); }
}  // namespace BO
using namespace BO;
namespace NT {
template <class T>
inline T lowbit(T x) {
  return x & -x;
}
template <class T>
inline T GCD(T A, T B) {
  T C;
  while (B != 0) C = B, B = A % B, A = C;
  return A;
}
template <class T>
inline T LCM(T A, T B) {
  return A * (B / GCD(A, B));
}
template <class T>
inline T Mod(T a, T b) {
  a %= b;
  return a < 0 ? a + b : a;
}
template <class T>
inline T MulMod(T a, T b, T c) {
  if (c == 1) return 0;
  if (c <= 0) return -1;
  T ret = 0, tmp;
  tmp = a = Mod(a, c);
  b = Mod(b, c);
  while (b) {
    if (b & 0x1)
      if ((ret += tmp) >= c) ret -= c;
    if ((tmp <<= 1) >= c) tmp -= c;
    b >>= 1;
  }
  return ret;
}
template <class T, class Tb>
inline T PowMod(Tb a, T b, T c) {
  if (c == 1) return 0;
  if (c <= 0) return -1;
  a = Mod(a, (Tb)c);
  Tb ret(1L % c);
  while (b) {
    if (b & 0x1) ret = ret * a % c;
    a = a * a % c;
    b >>= 1;
  }
  return (T)ret;
}
template <class T>
inline T HPowMod(T a, T b, T c) {
  if (c == 1) return 0;
  if (c <= 0) return -1;
  a = Mod(a, c);
  T ret(1L % c);
  while (b) {
    if (b & 0x1) ret = MulMod(ret, a, c);
    a = MulMod(a, a, c);
    b >>= 1;
  }
  return ret;
}
template <class T, class Tb>
inline T Pow(T a, Tb b) {
  T c(1);
  while (b) {
    if (b & 1) c *= a;
    a *= a, b >>= 1;
  }
  return c;
}
template <class T>
inline T EXT_GCD(T a, T b, T &x, T &y) {
  T t, ret;
  if (!b) {
    x = 1, y = 0;
    return a;
  }
  ret = EXT_GCD(b, a % b, x, y);
  t = x, x = y, y = t - a / b * y;
  return ret;
}
template <class T>
inline T Inv(T a, T n) {
  if (n <= 0) return -1;
  T d, x, y;
  d = EXT_GCD(a, n, x, y);
  if (d != 1) return -1;
  return Mod(x, n);
}
template <class T, int MAXN, T MOD = -1>
class Matrix {
 public:
  T m[MAXN][MAXN];
  Matrix() {}
  void init(T num[MAXN][MAXN]) {
    for (int i = 0; i < MAXN; i++) {
      for (int j = 0; j < MAXN; j++) {
        m[i][j] = num[i][j];
        if (MOD != -1) m[i][j] %= MOD;
      }
    }
  }
  friend Matrix operator*(const Matrix &m1, const Matrix &m2) {
    int i, j, k;
    Matrix ret;
    memset(ret.m, 0, sizeof(ret.m));
    for (i = 0; i < MAXN; i++) {
      for (j = 0; j < MAXN; j++)
        if (m1.m[i][j]) {
          for (k = 0; k < MAXN; k++) {
            ret.m[i][k] += m1.m[i][j] * m2.m[j][k];
            if (MOD != -1) ret.m[i][k] %= MOD;
          }
        }
    }
    return ret;
  }
  friend Matrix operator+(const Matrix &m1, const Matrix &m2) {
    int i, j;
    Matrix ret;
    for (i = 0; i < MAXN; i++) {
      for (j = 0; j < MAXN; j++) {
        ret.m[i][j] = 0;
        ret.m[i][j] = m1.m[i][j] + m2.m[i][j];
        if (MOD != -1) ret.m[i][j] %= MOD;
      }
    }
    return ret;
  }
  friend Matrix operator^(const Matrix &_M, long long nx) {
    Matrix ret, M(_M);
    for (int i = 0; i < MAXN; i++) {
      for (int j = 0; j < MAXN; j++) {
        if (i == j)
          ret.m[i][j] = 1;
        else
          ret.m[i][j] = 0;
      }
    }
    while (nx) {
      if (nx & 1) ret = ret * M;
      nx = nx >> 1;
      M = M * M;
    }
    return ret;
  }
};
}  // namespace NT
using namespace NT;
namespace Date {
int days[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
struct date {
  int year, month, day;
};
inline int leap(int year) {
  return (year % 4 == 0 && year % 100 != 0) || year % 400 == 0;
}
inline int legal(date a) {
  if (a.month < 0 || a.month > 12) return 0;
  if (a.month == 2) return a.day > 0 && a.day <= 28 + leap(a.year);
  return a.day > 0 && a.day <= days[a.month - 1];
}
inline int datecmp(date a, date b) {
  if (a.year != b.year) return a.year - b.year;
  if (a.month != b.month) return a.month - b.month;
  return a.day - b.day;
}
int weekday(date a) {
  int tm = a.month >= 3 ? (a.month - 2) : (a.month + 10);
  int ty = a.month >= 3 ? a.year : (a.year - 1);
  return (ty + ty / 4 - ty / 100 + ty / 400 + (int)(2.6 * tm - 0.2) + a.day) %
         7;
}
int date2int(date a) {
  int ret = a.year * 365 + (a.year - 1) / 4 - (a.year - 1) / 100 +
            (a.year - 1) / 400,
      i;
  days[1] += leap(a.year);
  for (i = 0; i < a.month - 1; ret += days[i++])
    ;
  days[1] = 28;
  return ret + a.day;
}
date int2date(int a) {
  date ret;
  ret.year = a / 146097 * 400;
  for (a %= 146097; a >= 365 + leap(ret.year);
       a -= 365 + leap(ret.year), ret.year++)
    ;
  days[1] += leap(ret.year);
  for (ret.month = 1; a >= days[ret.month - 1];
       a -= days[ret.month - 1], ret.month++)
    ;
  days[1] = 28;
  ret.day = a + 1;
  return ret;
}
}  // namespace Date
namespace IO {
template <class T>
inline T RD(T &x) {
  char c;
  for (c = getchar(); c < '-'; c = getchar())
    ;
  if (c == '-') {
    x = '0' - getchar();
    for (c = getchar(); '0' <= c && c <= '9'; c = getchar())
      x = x * 10 + '0' - c;
  } else {
    x = c - '0';
    for (c = getchar(); '0' <= c && c <= '9'; c = getchar())
      x = x * 10 + c - '0';
  }
  return x;
}
inline long long RD() {
  long long x;
  return RD(x);
}
}  // namespace IO
using namespace IO;
const int NN = (1 << 20) + 10;
int n, m, k;
long long x[25], y[25];
long long a[NN];
void build(int l, int r, int dep) {
  if (l == r) {
    return;
  } else {
    int mid = (l + r) / 2;
    build(l, mid, dep - 1);
    build(mid + 1, r, dep - 1);
    for (int i = l; i <= mid; i++) {
      x[dep] += upper_bound(a + mid + 1, a + r + 1, a[i] - 1) - (a + mid + 1);
      y[dep] += a + r + 1 - lower_bound(a + mid + 1, a + r + 1, a[i] + 1);
    }
    sort(a + l, a + r + 1);
  }
}
int main() {
  k = RD();
  n = 1 << k;
  for (int i = 1; i <= n; i++) {
    a[i] = RD();
  }
  build(1, n, k);
  m = RD();
  for (int i = 0; i < m; i++) {
    int t = RD();
    for (int i = 0; i <= t; i++) swap(x[i], y[i]);
    long long sum = 0;
    for (int i = 0; i < 25; i++) sum += x[i];
    printf("%I64d\n", sum);
  }
  return 0;
}
