[R59C]淘汰赛 - 代码源竞赛平台

时空限制

1S/512M

题目描述

有 $n$ 名选手（编号 $1$ 到 $n$）参加一场淘汰赛。每名选手都有一份预定的行动计划，打算在某个特定的时刻淘汰一名指定的对手。

具体规则如下：

1. 每名选手 $i$ 都有一个目标 $p_i$ 和一个行动时刻 $t_i$（保证 $t_i$ 互不相同）。
2. 只有当选手 $i$ 在时刻 $t_i$ 时仍然在场（即未被他人淘汰），他才能成功执行计划，将选手 $p_i$ 淘汰。如果选手 $p_i$ 在被选手 $i$ 淘汰之前，已经因为其他人的行动而被淘汰了，那么选手 $i$ 在时刻 $t_i$ 的行动将不会产生额外影响（但他本人只要在场，仍被视为“执行过”了计划）。
3. 如果选手 $i$ 在时刻 $t_i$ 之前（或恰好在 $t_i$ 时刻）已经被他人淘汰，他的行动计划将自动取消，不再对 $p_i$ 产生任何影响。

现在给出所有选手的目标和计划行动时刻，请你计算每名选手最终被淘汰的具体时刻。

格式

输入格式

第一行包含一个整数 $n$，表示选手的数量。

第二行包含 $n$ 个整数，第 $i$ 个整数代表 $p_i$，表示选手 $i$ 计划淘汰的目标编号。

第三行包含 $n$ 个整数，第 $i$ 个整数代表 $t_i$，表示选手 $i$ 计划行动的时刻。

输出格式

输出 $n$ 行，每行一个整数。

第 $i$ 行的整数表示选手 $i$ 被淘汰的时刻。如果选手 $i$ 最终没有被淘汰，则输出 $-1$。

样例

样例输入 #1

4
2 3 4 1
10 5 8 2

样例输出 #1

2
-1
5
-1

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$
$1$	$30$	$2000$
$2$	$70$	$2 \times 10^5$

对于 $100\%$ 的数据，$2 \le n \le 2 \times 10^5$，$1 \le p_i \le n$ 且 $p_i \neq i$，$1 \le t_i \le 10^9$，且所有的 $t_i$ 互不相同。