L. Синий Трактор Airlines
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
По полям, по полям

Синий трактор едет к нам,

У него в прицепе

Кто-то песенку поёт!

— Синий трактор
Синий трактор едет по полям, пронумерованным натуральными числами и поёт песню. На полях его ждёт $$$n$$$ животных, $$$i$$$-е животное — на поле $$$a_i$$$. Все $$$a_i$$$ различны. У каждого животного есть ровно один ценитель. Ценители также находятся на некоторых полях $$$b_i$$$. Все $$$b_i$$$ также различны. Относительный порядок животных совпадает с относительным порядком ценителей. Более формально: $$$a_i \lt a_j \Leftrightarrow b_i \lt b_j$$$, для всех $$$1\le i, j\le n$$$.

Синий трактор хочет $$$q$$$ раз проехать по полям. Каждый раз он проедет от поля $$$s_i$$$ до поля $$$t_i$$$ и посадит в свой прицеп всех животных, которых встретит. Если животное едет в прицепе Синего трактора и оказывается на одном поле со своим ценителем, то этот ценитель начинает подпевать Синему трактору. Когда трактор доезжает до конца своего пути, он высаживает всех животных на этом поле, а все ценители прекращают петь.

Все $$$a_i$$$, $$$b_j$$$, $$$s_l$$$, $$$t_k$$$ $$$(1 \le i, j \le n)$$$ $$$(1 \le l, k \le q)$$$ различны.

Для каждого проезда Синего трактора определите количество ценителей, которые пели во время этого проезда.

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

В первой строке содержится число $$$n\ (1 \le n \le 2 \cdot 10^5)$$$ — количество животных (и их ценителей).

Во второй строке содержатся $$$n$$$ чисел $$$a_i\ (1 \le a_i \le 10^9)$$$ — координаты животных.

В третьей строке содержатся $$$n$$$ чисел $$$b_i\ (1 \le b_i \le 10^9)$$$ — координаты ценителей.

В четвертой строке содержится число $$$q\ (1 \le q \le 2 \cdot 10^5)$$$ — количество проездов Синего трактора.

В следующих $$$q$$$ строках содержится по $$$2$$$ числа: $$$s$$$ и $$$t$$$ $$$(1 \le s, t \le 10^9)$$$ — координаты начала и конца пути Синего трактора.

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

Для каждого из $$$q$$$ запросов выведите ответ на задачу. Ответы разделяйте переводом строки.

Пример
Входные данные
3
2 8 11
4 6 13
3
7 15
20 5
1 9
Выходные данные
1
2
2