← 返回题目列表

Codeforces · 227/B

B. 有效的方法

中文机器翻译题面 查看原题

在团队训练 Vasya 时,Petya 和 Sasha 遇到了在数组中实现线性搜索的问题。

根据男孩们的说法,线性搜索的工作原理如下。依次将预先选择的顺序中的数组元素与您需要查找的数字进行比较。一旦找到与所需元素相等的数组元素,搜索就结束。算法的效率是执行比较的次数。线性搜索进行的比较越少,它就越有效。

Vasya 认为,如果线性搜索按顺序迭代元素,从第 1 个元素开始(在本问题中,我们考虑从 1 到 n 索引的数组元素)并以第 n 个元素结束,那么线性搜索效果会更好。 Petya 说 Vasya 是错误的:如果搜索按顺序迭代从第 n 个开始到第 1 个结束的元素,则搜索将需要更少的比较。萨沙认为这两种方法是等效的。

为了最终开始任务,队友们决定解决争论并通过一个例子比较这两种方法。为此,他们采用了一个从 1 到 n 的整数排列数组,并生成了 m 个以下形式的查询:在数组中查找值为 bi 的元素。他们想要计算这两种方法线性搜索响应所有查询总共需要多少次比较。如果第一次搜索需要较少的比较,那么争议的胜利者是 Vasya。如果第二个成功,那么获胜者就是 Petya。如果两种方法进行相同数量的比较,那么萨沙就占上风。

但问题是,线性搜索太慢了。这就是为什么男孩们不会在训练结束之前知道谁是对的,除非你进来。帮助他们确定谁将赢得这场争论。

输入

第一行包含整数 n (1 ≤ n ≤ 105) — 数组中的元素数量。第二行包含 n 个不同的空格分隔整数 a1, a2, ..., an (1 ≤ ai ≤ n) — 数组的元素。

第三行包含整数 m (1 ≤ m ≤ 105) — 查询数量。最后一行包含 m 个空格分隔的整数 b1, b2, ..., bm (1 ≤ bi ≤ n) — 搜索查询。请注意,查询可以重复。

输出

打印两个整数,显示 Vasya 的方法需要多少次比较以及 Petya 的方法需要多少次比较。用空格分隔数字。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

2
1 2
1
1

输出 #1

1 2

输入 #2

2
2 1
1
1

输出 #2

2 1

输入 #3

3
3 1 2
3
1 2 3

输出 #3

6 6

注意

在第一个示例中,Vasya 的方法将进行一次比较(从第一个元素开始,立即找到所需的数字),而 Petya 的方法将进行两次比较(首先与第二个数组元素进行比较,没有找到搜索项,然后与第一个元素进行比较)。

相反,在第二个示例中,Vasya 的方法将需要两次比较(首先与第一个元素,然后与第二个元素),而 Petya 的方法将在一次比较中找到所需的值(第一次与第二个元素比较)。