B. Игра на выбывание
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бесси снимает шоу под названием Мудзюцу Коусен. Для одного из выпусков она приглашает $$$n$$$ волшебников и выстраивает их в ряд слева направо. Изначальный уровень мастерства $$$i$$$-го волшебника равен $$$a_i$$$.

Волшебники участвуют в турнире по системе «царь горы». Самый левый из оставшихся волшебников становится первым чемпионом, а его текущий уровень мастерства равен изначальному.

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

Если $$$s \lt x$$$, чемпион отказывается от боя. Следующий волшебник становится новым чемпионом с уровнем мастерства $$$x$$$.

В противном случае чемпион вступает в бой и побеждает (при $$$s = x$$$ чемпион также побеждает). В этом случае текущий уровень мастерства чемпиона становится равен $$$s+x$$$.

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

Дана перестановка $$$p_1,p_2,\ldots,p_n$$$ целых чисел от $$$1$$$ до $$$n$$$. Для каждого $$$0 \le i \le n-1$$$ Бесси убирает из строя волшебников $$$p_1,p_2,\ldots,p_i$$$. Если $$$i=0$$$, ни один волшебник не убирается. Относительный порядок всех оставшихся волшебников не изменяется.

Для каждого такого $$$i$$$ определите, сколько отказов от боя произойдёт, если Бесси проведёт турнир только среди оставшихся волшебников.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

Во второй строке каждого набора входных данных содержатся $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$).

В третьей строке каждого набора входных данных содержится перестановка $$$p_1,p_2,\ldots,p_n$$$ целых чисел от $$$1$$$ до $$$n$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел.

$$$i$$$-е число должно быть равно количеству отказов от боя после удаления волшебников $$$p_1,p_2,\ldots,p_{i-1}$$$.

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

В первом наборе входных данных ответы равны $$$2,1,0,0$$$.

До каких-либо удалений массив имеет вид $$$[1,2,4,3]$$$. Чемпион с уровнем мастерства $$$1$$$ отказывается от боя с волшебником уровня $$$2$$$, а затем чемпион с уровнем мастерства $$$2$$$ отказывается от боя с волшебником уровня $$$4$$$. Чемпион с уровнем мастерства $$$4$$$ побеждает волшебника уровня $$$3$$$, поэтому происходит $$$2$$$ отказа от боя.

После удаления волшебника $$$1$$$ остаётся массив $$$[2,4,3]$$$. Чемпион с уровнем мастерства $$$2$$$ отказывается от боя с волшебником уровня $$$4$$$, а затем чемпион с уровнем мастерства $$$4$$$ побеждает волшебника уровня $$$3$$$, поэтому происходит $$$1$$$ отказ от боя.

После удаления волшебников $$$1$$$ и $$$2$$$ остаётся массив $$$[4,3]$$$. Чемпион побеждает единственного оставшегося волшебника, поэтому происходит $$$0$$$ отказов от боя. После удаления волшебников $$$1$$$, $$$2$$$ и $$$3$$$ остаётся только один волшебник, поэтому также происходит $$$0$$$ отказов от боя.

Во втором наборе входных данных ответы равны $$$1,0,2,1,0$$$.

До каких-либо удалений массив имеет вид $$$[3,1,7,2,6]$$$. Чемпион с уровнем мастерства $$$3$$$ побеждает волшебника уровня $$$1$$$ и получает одно очко мастерства, а затем отказывается от боя с волшебником уровня $$$7$$$. После этого чемпион побеждает волшебников уровней $$$2$$$ и $$$6$$$, поэтому происходит $$$1$$$ отказ от боя.

После удаления волшебника $$$3$$$, уровень мастерства которого равен $$$7$$$, остаётся массив $$$[3,1,2,6]$$$. Чемпион побеждает каждого оставшегося волшебника, поэтому происходит $$$0$$$ отказов от боя.

После удаления также волшебника $$$1$$$ остаётся массив $$$[1,2,6]$$$. Чемпион с уровнем мастерства $$$1$$$ отказывается от боя с волшебником уровня $$$2$$$, а затем чемпион с уровнем мастерства $$$2$$$ отказывается от боя с волшебником уровня $$$6$$$, поэтому происходит $$$2$$$ отказа от боя.

После удаления также волшебника $$$5$$$ остаётся массив $$$[1,2]$$$. Происходит $$$1$$$ отказ от боя. Наконец, после удаления также волшебника $$$2$$$ остаётся только один волшебник, поэтому происходит $$$0$$$ отказов от боя.