C. Исчезающая перестановка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перестановка целых чисел от $$$1$$$ до $$$n$$$ — это массив размером $$$n$$$, в котором каждое целое число от $$$1$$$ до $$$n$$$ встречается ровно один раз.

Вам дана перестановка $$$p$$$ целых чисел от $$$1$$$ до $$$n$$$. Вам нужно обработать $$$n$$$ запросов. В ходе $$$i$$$-го запроса вы заменяете $$$p_{d_i}$$$ на $$$0$$$. Каждый элемент заменяется на $$$0$$$ ровно один раз. Изменения, которые вносят запросы, сохраняются, то есть после $$$i$$$-го запроса все числа $$$p_{d_1}, p_{d_2}, \dots, p_{d_i}$$$ будут нулями.

После каждого запроса вам нужно вычислить минимальное количество операций, необходимых для исправления массива, другими словами, чтобы преобразовать текущий массив в какую-либо перестановку целых чисел от $$$1$$$ до $$$n$$$ (возможно, в исходную перестановку $$$p$$$, возможно, в какую-то другую перестановку).

Операция, которую вы можете выполнять для исправления массива, следующая:

  • выбрать целое число $$$i$$$ от $$$1$$$ до $$$n$$$, заменить $$$i$$$-й элемент массива на $$$i$$$.

Обратите внимание, что ответ для каждого запроса вычисляется независимо, то есть вы фактически не выполняете никаких операций, просто вычисляете минимальное количество операций.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^{5}$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_{i} \le n$$$) — исходная перестановка. Все $$$p_i$$$ различны.

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$d_1, d_2, \dots, d_n$$$ ($$$1 \le d_{i} \le n$$$). Все $$$d_{i}$$$ различны.

Дополнительное ограничение на входные данные:

  • сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^{5}$$$.
Выходные данные

Для каждого набора входных данных выведите строку, содержащую $$$n$$$ целых чисел, где $$$i$$$-е целое число должно быть равно минимальному количеству операций, необходимых для исправления массива, который был получен после $$$i$$$-го запроса (то есть перестановки $$$p$$$, где все числа $$$p_{d_1}, p_{d_2}, \dots, p_{d_i}$$$ заменены на нули).

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

В первом наборе входных данных после каждого запроса каждое целое число, которое было заменено на $$$0$$$, можно восстановить за одну операцию.

Во втором наборе входных данных вы можете действовать следующим образом:

  • Запрос $$$1$$$: $$$p = [4, 5, 3, 0, 2]$$$, его можно преобразовать в $$$[{\color{red}1}, 5, 3, {\color{red}4}, 2]$$$.
  • Запрос $$$2$$$: $$$p = [4, 5, 3, 0, 0]$$$, его можно преобразовать в $$$[{\color{red}1}, {\color{red}2}, 3, {\color{red}4}, {\color{red}5}]$$$.
  • Запрос $$$3$$$: $$$p = [0, 5, 3, 0, 0]$$$, его можно преобразовать в $$$[{\color{red}1}, {\color{red}2}, 3, {\color{red}4}, {\color{red}5}]$$$.
  • Запрос $$$4$$$: $$$p = [0, 5, 0, 0, 0]$$$, его можно преобразовать в $$$[{\color{red}1}, {\color{red}2}, {\color{red}3}, {\color{red}4}, {\color{red}5}]$$$.
  • Запрос $$$5$$$: $$$p = [0, 0, 0, 0, 0]$$$, его можно преобразовать в $$$[{\color{red}1}, {\color{red}2}, {\color{red}3}, {\color{red}4}, {\color{red}5}]$$$.

Числа, которые были изменены, выделены красным.