#5322. 会议座位

    ID: 5322 传统题 1000ms 256MiB 尝试: 11 已通过: 1 难度: 3 上传者: 标签>数据结构树状数组逆序对map归并排序普及/提高−

会议座位

题目背景

话说校长最近很喜欢召开全校教职工大会,让老师们强行听他装逼。

题目描述

现在校长在校园网上公布了一份座位表,nn 位老师从左到右依次排成一行。老师们都对这个座位很满意。

然而到了开会时,校长不小心把座位表打乱了,老师们很不满。老师们并不在意自己的位置变了多少,但如果有一对老师 aabb,他们原来的座位是 aabb 左边,现在变成了 aabb 右边,那么这一对老师便会贡献一单位不满值。

校长想知道这些老师的总不满值是多少。

输入格式

第一行一个正整数 nn,表示老师的人数。

第二行有 nn 个字符串,每个字符串代表老师的名字(大小写敏感)。这一行代表原来的座位表,名字之间用空格隔开。

第三行有 nn 个字符串,代表打乱后的座位表,名字之间用空格隔开。

输出格式

一行,一个正整数,表示老师们的总不满值。

样例

3
Stan Kyle Kenny
Kyle Stan Kenny
1
5
A B C D E
B A D E C
3

数据范围

  • 对于 80%80\% 的数据:1n1031 \le n \le 10^3
  • 对于 100%100\% 的数据:1n1051 \le n \le 10^5,每位老师名字长度不超过 55,只含大小写字母且互不相同,大小写敏感。