Бимоху, начальнику Машмоха, Машмох не нравился. Вот он его и уволил. Решил тогда Машмох новую работу не искать, а поступить в университет и поучаствовать в 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 и все запросы. Ответьте на все запросы. Обратите внимание, что изменения от запроса сохраняются для последующих запросов.
Выходные данные
Выведите m строк. В i-й строке выведите ответ (количество инверсий) на i-й запрос.
Примечание
При выполнении реверса массива 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].
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2 1 4 3
4
1 2 0 2
|
0
6
6
0
|
|
2
|
1
1 2
3
0 1 1
|
0
1
0
|