CF2262B.Culling Game

Bessie is making a show called Moojutsu Cowsen. For one episode, she invites $n$ sorcerers and lines them up from left to right. The initial skill level of the $i$-th sorcerer is $a_i$.

The sorcerers compete in a king-of-the-hill tournament. The leftmost remaining sorcerer starts as the champion, and his current skill is equal to his initial skill.

Then, the champion faces each remaining sorcerer to his right, one by one. Suppose the current champion has skill $s$, and the next sorcerer has skill $x$.

If $s \lt x$, the champion forfeits. The next sorcerer becomes the new champion with skill $x$.

Otherwise, the champion fights and wins (the champion still wins when $s = x$). In this case, the champion's current skill becomes $s+x$.

Bessie finds forfeits boring, so before running the tournament, she may remove some sorcerers from the lineup.

You are given a permutation $p_1,p_2,\ldots,p_n$ of the integers from $1$ to $n$. For each $0 \le i \le n-1$, Bessie removes sorcerers $p_1,p_2,\ldots,p_i$ from the lineup. If $i=0$, no sorcerers are removed. The relative order of all remaining sorcerers does not change.

For each such $i$, determine how many forfeits happen when Bessie runs the tournament using only the remaining sorcerers.

贝茜正在制作一档名为《哞术牛生》的节目。在其中一集里，她邀请了 $n$ 位法师，并将他们从左到右排成一列。第 $i$ 位法师的初始技能值为 $a_i$。

这些法师将进行一场“山顶之王”式淘汰赛。剩余法师中最左侧的一位首先成为冠军，其当前技能值等于其初始技能值。

随后，冠军依次挑战其右侧所有尚未被淘汰的法师。假设当前冠军的技能值为 $s$，下一位法师的技能值为 $x$：

• 若 $s \lt x$，则冠军弃权；下一位法师成为新冠军，其技能值为 $x$；
• 否则（即 $s \ge x$），冠军出战并获胜（当 $s = x$ 时也视为获胜）；此时冠军的当前技能值更新为 $s+x$。

贝茜觉得弃权环节很无趣，因此在正式举办比赛前，她可以预先从队列中移除若干法师。

你将获得一个 $1$ 到 $n$ 的排列 $p_1,p_2,\ldots,p_n$。对每个 $0 \le i \le n-1$，贝茜会从队列中移除编号为 $p_1,p_2,\ldots,p_i$ 的法师（若 $i=0$，则不移除任何法师）。所有未被移除的法师保持原有相对顺序。

对每个这样的 $i$，请计算：仅使用剩余法师运行上述比赛时，总共会发生多少次弃权。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2\cdot 10^5$).

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$).

The third line of each test case contains a permutation $p_1,p_2,\ldots,p_n$ of the integers from $1$ to $n$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$）。

每个测试用例的第三行包含一个 $1$ 到 $n$ 的排列 $p_1,p_2,\ldots,p_n$。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, output $n$ integers.

The $i$-th integer should be the number of forfeits after removing sorcerers $p_1,p_2,\ldots,p_{i-1}$.

对于每个测试用例，输出 $n$ 个整数。

第 $i$ 个整数应为移除巫师 $p_1, p_2, \ldots, p_{i-1}$ 后的弃权次数。

For the first test case, the answers are $2,1,0,0$.

Before any removals, the array is $[1,2,4,3]$. The champion with skill $1$ forfeits against skill $2$, and then the champion with skill $2$ forfeits against skill $4$. The champion with skill $4$ defeats skill $3$, so there are $2$ forfeits.

After removing sorcerer $1$, the remaining array is $[2,4,3]$. The champion with skill $2$ forfeits against skill $4$, and then the champion with skill $4$ defeats skill $3$, so there is $1$ forfeit.

After removing sorcerers $1$ and $2$, the remaining array is $[4,3]$. The champion defeats the only remaining sorcerer, so there are $0$ forfeits. After removing sorcerers $1$, $2$, and $3$, only one sorcerer remains, so there are also $0$ forfeits.

For the second test case, the answers are $1,0,2,1,0$.

Before any removals, the array is $[3,1,7,2,6]$. The champion with skill $3$ defeats skill $1$ and gains one skill point, then forfeits against skill $7$. After that, the champion defeats skills $2$ and $6$, so there is $1$ forfeit.

After removing sorcerer $3$, whose skill is $7$, the remaining array is $[3,1,2,6]$. The champion defeats every remaining sorcerer, so there are $0$ forfeits.

After also removing sorcerer $1$, the remaining array is $[1,2,6]$ The champion with skill $1$ forfeits against skill $2$, and then the champion with skill $2$ forfeits against skill $6$, so there are $2$ forfeits.

After also removing sorcerer $5$, the remaining array is $[1,2]$. There is $1$ forfeit. Finally, after also removing sorcerer $2$, only one sorcerer remains, so there are $0$ forfeits.

对于第一个测试用例，答案为 $2,1,0,0$。

在任何移除操作之前，数组为 $[1,2,4,3]$。技能值为 $1$ 的冠军输给技能值为 $2$ 的冠军，随后技能值为 $2$ 的冠军又输给技能值为 $4$ 的冠军。技能值为 $4$ 的冠军击败技能值为 $3$ 的冠军，因此共发生 $2$ 次弃权（forfeit）。

移除第 $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$ 的冠军并获得 $1$ 点技能值，随后输给技能值为 $7$ 的冠军。之后，该冠军（此时技能值为 $4$）击败技能值为 $2$ 和 $6$ 的冠军，因此共发生 $1$ 次弃权。

移除技能值为 $7$ 的第 $3$ 位术士后，剩余数组为 $[3,1,2,6]$。冠军击败所有剩余术士，因此共发生 $0$ 次弃权。

再移除第 $1$ 位术士后，剩余数组为 $[1,2,6]$。技能值为 $1$ 的冠军输给技能值为 $2$ 的冠军，随后技能值为 $2$ 的冠军又输给技能值为 $6$ 的冠军，因此共发生 $2$ 次弃权。

再移除第 $5$ 位术士后，剩余数组为 $[1,2]$，共发生 $1$ 次弃权。最后，再移除第 $2$ 位术士后，仅剩一位术士，因此共发生 $0$ 次弃权。