C. Машмох и операция реверс
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
stdin
вывод
stdout

Бимоху, начальнику Машмоха, Машмох не нравился. Вот он его и уволил. Решил тогда Машмох новую работу не искать, а поступить в университет и поучаствовать в ACM. Машмох хочет попасть в команду Бамоха. Для этого ему дали (в качестве испытания) несколько задач по программированию и неделю на их решение. Машмох не шибко умудренный программист. В общем-то, он и не программист вовсе. Так что ничего он не решил, а попросил вас помочь ему с этими заданиями. Одно из них такое:

Вам дан массив a длины 2n, а также m запросов. Запрос номер i характеризуется целым числом qi. В ответ на i-й запрос вы должны выполнить последовательность операций:

  • разбить массив на 2n - qi частей, где каждая часть — подмассив, состоящий из 2qi чисел; j-й подмассив (1 ≤ j ≤ 2n - qi) должен содержать элементы a[(j - 1)·2qi + 1], a[(j - 1)·2qi + 2], ..., a[(j - 1)·2qi + 2qi];
  • выполнить реверс элементов каждого подмассива;
  • склеить все подмассивы в один массив в том же порядке (этот массив станет новым массивом a);
  • вывести количество инверсий в новом массиве a.

Вам дан исходный массив a и все запросы. Ответьте на все запросы. Обратите внимание, что изменения от запроса сохраняются для последующих запросов.

Входные данные

В первой строке записано единственное целое число n (0 ≤ n ≤ 20).

Во второй строке записано 2n целых чисел через пробел a[1], a[2], ..., a[2n] (1 ≤ a[i] ≤ 109), исходный массив.

В третьей строке записано единственное целое число m (1 ≤ m ≤ 106).

В четвертой строке записано m целых чисел через пробел q1, q2, ..., qm (0 ≤ qi ≤ n) — запросы.

Обратите внимание: входные и выходные данные имеют очень большой размер, поэтому не стоит использовать медленные методы ввода и вывода данных вашего языка программирования. Например, в языке C++ не стоит использовать потоки ввода и вывода (cin, cout).

Выходные данные

Выведите m строк. В i-й строке выведите ответ (количество инверсий) на i-й запрос.

Примеры
Входные данные
2
2 1 4 3
4
1 2 0 2
Выходные данные
0
6
6
0
Входные данные
1
1 2
3
0 1 1
Выходные данные
0
1
0
Примечание

При выполнении реверса массива x[1], x[2], ..., x[n] получается новый массив y[1], y[2], ..., y[n], где y[i] = x[n - i + 1] для каждого i.

Количество инверсий массива x[1], x[2], ..., x[n] — это количество пар индексов i, j, таких, что: i < j и x[i] > x[j].