410266: GYM103994 H Башенки

H. Башенкиограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Недавно в самом центре Флатляндии построили $$$n$$$ невероятно красивых башен, $$$i$$$-я из которых находится в точке $$$x_i$$$ и имеет высоту $$$y_i$$$, а так же очень высокий отель в точке $$$0$$$. В отеле $$$q$$$ номеров и $$$j$$$-й из них находится на высоте $$$h_j$$$.

Хозяин отеля ещё не определился с ценами номеров. Он убежден, что чем больше башен можно увидеть из номера, тем больше за него готовы платить, а потому поручил вам для каждого номера посчитать, сколько башен можно увидеть из него.

В этой задаче можно считать, что башни — это отрезки на плоскости, с координатами концов $$$(x_i, 0)$$$ и ($$$x_i, y_i$$$) соответственно. Номер в отеле — это точка с координатами $$$(0, h_j)$$$.

Башню $$$i$$$ видно из номера отеля $$$j$$$, если на отрезке $$$\{(x_i, 0)$$$, $$$(x_i, y_i)\}$$$ есть точка $$$(a, b)$$$, такая что отрезок $$$\{(0, h_j)$$$, $$$(a, b)\}$$$ не пересекается с отрезками других башен. Иными словами — на отрезке от отеля до какой-то точки башни ничего нет.

Обратите внимание: отрезки пересекаются, если имеют хотя бы одну общую точку, в том числе если их общая точка — конец какого-то из отрезков.

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

В первой строке входных данных находится одно целое число $$$n$$$ ($$$1 \le n \le 200\,000$$$) — количество построенных башен.

В следующих $$$n$$$ строках даны описания башен:

В $$$i$$$-й из них находятся два целых числа $$$x_i$$$ и $$$y_i$$$ $$$(1 \le x_i, y_i \le 10^9, x_i \neq x_j$$$ при $$$i \neq j)$$$ — позиция и высота $$$i$$$-й башни соответственно.

В следующей строке дано одно целое число $$$q$$$ $$$(1 \le q \le 200\,000)$$$ — количество номеров в отеле.

В следующих $$$q$$$ строках даны описания комнат в отеле:

В $$$j$$$-й из них находится единственное целое число $$$h_j$$$ $$$(1 \le h_j \le 10^9)$$$ — высота $$$j$$$-го номера в отеле.

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

Выведите $$$q$$$ чисел. Для каждой комнаты в отеле — количество башен, которые видно из неё.

ПримерыВходные данные

3
2 1
1 2
4 4
4
3
4
1
2

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

2
3
1
2

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

4
5 4
8 3
10 7
4 4
4
4
1
8
5

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

2
1
4
3

Примечание

В тестовом примере 1 всего 4 запроса, вот иллюстрация каждого: