CF227B Effective Approach

在一次团队训练中，Vasya、Petya 和 Sasha 遇到了一道关于实现数组线性查找的问题。 按照男孩们的说法，线性查找的工作方式如下。按某个预先选择的顺序，依次将数组元素与要查找的数字进行比较。一旦找到了与所需数相等的数组元素，查找就结束。算法的效率取决于进行了多少次比较。比较次数越少，线性查找的效率就越高。 Vasya 认为，如果线性查找从第 $1$ 个元素开始，按顺序遍历元素直到第 $n$ 个元素，效果会更好（本题中数组下标从 $1$ 到 $n$）。而 Petya 却说 Vasya 错了：如果线性查找从第 $n$ 个元素开始，按顺序遍历到第 $1$ 个元素，所需的比较次数会更少。Sasha 则认为这两种方法其实是等价的。 为了结束争论并开始题目，队友们决定在一个例子上比较这两种方法。为此，他们取了一个 $1$ 到 $n$ 的排列作为数组，并生成了 $m$ 个查询，每个查询为：在数组中查找值为 $b_{i}$ 的元素。他们想计算出，对于两种方法，线性查找处理所有查询所需的总比较次数。如果第一种方法比较次数更少，则 Vasya 赢；如果第二种方法更少，则 Petya 赢；如果两种方法需要的比较次数相同，则 Sasha 赢。 问题在于，线性查找太慢了。如果不用你的帮助，男孩们在训练结束前都搞不清谁是对的。请帮助他们判断谁能赢得争论。

第一行包含整数 $n$ $(1 \leq n \leq 10^{5})$，表示数组中的元素个数。第二行包含 $n$ 个互不相同的用空格分隔的整数 $a_{1}, a_{2}, \ldots, a_{n}$ $(1 \leq a_{i} \leq n)$，表示数组的元素。 第三行包含整数 $m$ $(1 \leq m \leq 10^{5})$，表示查询个数。最后一行包含 $m$ 个用空格分隔的整数 $b_{1}, b_{2}, \ldots, b_{m}$ $(1 \leq b_{i} \leq n)$，表示查询。注意，查询可以重复。

输出两个整数，分别表示 Vasya 方案和 Petya 方案需要的总比较次数，中间用空格隔开。 请不要在 C++ 中用 %lld 格式读写 64 位整数。推荐使用 cin、cout 流或 %I64d 格式。

在第一个样例中，Vasya 的方案只需要一次比较（从第 $1$ 个元素开始，立刻找到目标），而 Petya 的方案需要两次比较（先与第 $2$ 个元素比较，没有找到，再与第 $1$ 个元素比较）。 在第二个样例中，Vasya 的方案需要两次比较（先比较第 $1$ 个元素，再比较第 $2$ 个元素），而 Petya 的方案第一次比较第 $2$ 个元素就找到了目标，只需一次比较。 由 ChatGPT 5 翻译