Дистанционный практикум по программированию

Список с пропусками — структура данных, представляющая собой расширение упорядоченного односвязного списка дополнительными связями между элементами. Пример показан на следующем рисунке.

Как видно из рисунка, структура состоит из нескольких упорядоченных связных списков, при этом каждый узел может находиться одновременно в нескольких списках.

В список первого уровня (самый нижний на рисунке) входят все узлы. В нашем примере это список Header → 3 → 6 → 8 → 9 → 11 → 13 → End.

В список второго уровня входит лишь какая-то часть узлов. На рисунке это список Header → 6 → 9 → 11 → End.

Аналогично, в список каждого следующего уровня входит подмножество узлов предыдущего списка. В нашем примере список третьего уровня — это Header → 9 → 11 → End, список четвёртого уровня —  Header → 11 → End.

Для удобства реализации можно считать, что конечный узел всех списков End хранит значение больше любого, которое разрешено помещать в список. Аналогично, головной узел Header хранит значение меньше любого, которое разрешено помещать в список.

Вставка новых элементов в список с пропусками осуществляется вероятностным алгоритмом при помощи генератора случайных чисел. При этом обычно используется следующее правило: примерно половина элементов должна принадлежать только списку первого уровня, четверть элементов — спискам первого и второго уровня, одна восьмая — спискам первого, второго и третьего уровня и так далее. Общее количество уровней, таким образом, пропорционально log₂(N), где N — количество элементов.

Алгоритм поиска элемента начинает свою работу с головного узла и самого верхнего уровня и движется по ссылкам этого уровня слева направо. Встав на очередной узел, смотрим на узел, следующий после него. Если значение в нём равно искомому, алгоритм останавливается. Если значение в нём больше искомого, то опускаемся на уровень ниже (оставаясь в том же узле) и продолжаем поиск уже на этом уровне. Поиск останавливается либо когда найден искомый элемент, либо когда мы спустились до уровня 1 и дошли до элемента, больше искомого (это означает, что элемент в списке отсутствует).

В данной задаче вам дан готовый список с пропусками, а также набор запросов на поиск элемента. Для каждого запроса определите, какое количество спусков на нижележащие уровни будет сделано во время поиска. Например, для поиска числа 11 потребуется сделать 0 спусков, для поиска числа 18 (которого нет в списке) — 3 спуска.

Гарантируется, что список с пропусками сгенерирован вероятностным алгоритмом, и среднее время поиска одного элемента составляет O(log(N)).

 

Входные данные. Первая строка входных данных содержит целое число N (1 ≤ N ≤ 10⁵) — количество элементов структуры. Вторая строка содержит N пар разделенных пробелом целых чисел a_i, b_i  (−10⁶ ≤ a_i ≤ 10⁶, b_i ≥ 1), где a_i — значение в очередном узле, b_i  — число списков, проходящих через этот узел (максимальный уровень узла). Все числа a_i упорядочены по возрастанию.

В третьей строке находится целое число Q (1 ≤ Q ≤ 10⁵) —  количество запросов поиска. В четвертой строке располагается Q разделенных пробелом целых чисел q_i (−10⁶ ≤ q_i ≤ 10⁶) .

 

Выходные данные. Выведите Q целых чисел по одному в каждой строке — количество спусков, которое потребуется сделать при поиске каждого элемента.

 

Примеры

Входные данные	Выходные данные
6 3 1 6 2 8 1 9 3 11 4 13 1 2 11 18	0 3
4 0 3 3 2 4 2 5 3 5 3 5 0 -5 -1	1 0 0 2 2