3477 - 预言家(强化版)

题目描述

星际F4方程式飞艇联赛即将举行,来自全宇宙的飞艇手齐聚一堂,一较高下。

为了提升赛事的热度,举办方为飞艇迷们准备了赛事预测大奖,预测最准确的飞艇迷将获得飞艇一艘。

飞艇迷小 A 为了赢得赛前预测大奖,特地请教了知名占卜师吉罗拉莫·卡尔达诺,预测了所有选手的排名。

比赛结束后,正式的比赛结果终于公布在了星际日报上。小 A 想要计算一下预测得分。计算方法:
他需要在预测和实际排名中,找出有多少对赛车手 (A, B) 满足 A 总是排在 B 之前,对数即得分。
但是选手太多了,请你帮他计算一下得分。

输入

输入共三行。

  • 第一行是一个整数 n ,表示参赛选手总人数。
  • 第二行按照赛后排名,从前往后给出每个选手的名字。
  • 第三行按照赛前预测排名,从前往后给出每个选手的名字。

每位选手的名字仅包含小写英文字母,字母数在 3 到 15 之间。
输入保证每行中没有重复的名字,且第二行中的名字都在第三行中出现,反之亦然。

输出

输出只有一行,包含一个整数,即得分。

样例

输入

3
wangchao mahan zhanzhao
zhanzhao mahan wangchao

输出

0

输入

4
tom jerry jack sun
jerry jack tom sun

输出

4
说明

说明

样例 1 解释

没有满足要求的选手,所以得分为 0。

样例 2 解释

满足条件的选手对有:

  • (tom, sun)
  • (jerry, jack)
  • (jerry, sun)
  • (jack, sun)

共 4 对,所以得分为 4。

数据规模

  • 对于 30% 的数据, 1 \leq n \leq 500
  • 对于 50% 的数据, 1 \leq n \leq 10000
  • 对于 70% 的数据, 1 \leq n \leq 60000
  • 对于 100% 的数据, 1 \leq n \leq 100000
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 5
通过人数 2
金币数量 4 枚
难度 提高


上一题 下一题