Mirko-wan 刚刚收到了他的历史考试成绩。其中一道题目要求将著名的历史战役按时间顺序排列。正确顺序为:
- Blockade of Naboo 2. Battle of Geonosis 3. Battle of Yavin 4. Battle of Hoth 5. Battle of Endor
Mirko-wan 为这次考试做足了(相对而言的)准备,因此他记住了除 Blockade of Naboo 之外所有战役的确切年份。他完全不记得关于这场战役的任何信息,于是他随机地将其排在了最后而不是最前,得到的顺序为:
- Battle of Geonosis 2. Battle of Yavin 3. Battle of Hoth 4. Battle of Endor 5. Blockade of Naboo
由于 Mirko-wan 的排序在任何位置上都与正确答案不匹配,因此他在该题上的得分——令他非常失望——是 5 分中的 0 分,尽管他实际上知道五场战役中四场的正确相对顺序!
这引发了关于排序题如何公平评分的问题。上述例子表明,通过计算处于正确绝对位置的元素个数来评分并不公平。有没有更好的方法?
一种可能性是寻找正确排序元素的最长子序列(不一定连续)。但这也不是最好的解决方案:如果一个元素仅比正确顺序偏移了一个位置,它所带来的分数就会降为零,尽管它几乎是正确排序的。
因此,Mirko-wan 向他的历史老师提出了一种新的评分方法(采用 MAWT——不妨试试心理战术(Might As Well Try a Mind Trick)的方法)。对于任意两个元素,如果这两个元素之间的相对顺序正确,学生将获得 1 分。换句话说,得分就是学生排序正确的元素对(pair)的数量。当然,最大可能得分就是总对数,即 $N \times (N - 1) / 2$,其中 $N$ 是总元素个数。
输入格式
输入的第一行包含一个正整数 $N$($2 \le N \le 2500$),表示元素的数量。这些元素是互不相同的单词,由 3 到 15 个小写英文字母组成。
输入的第二行包含 $N$ 个元素,用空格隔开,按正确顺序排列。
输入的第三行包含 $N$ 个元素,用空格隔开,按 Mirko-wan 的排序排列。
输出格式
输出的第一行也是唯一一行必须包含(不含空格):Mirko-wan 使用他的评分方法所能获得的分数、一个斜杠字符 /,以及该题的最大可能得分(同样基于 Mirko-wan 的评分方法)。(这是典型阅卷考试中常见的记分格式。)
样例
输入样例 1
3 alpha beta gamma alpha gamma beta
输出样例 1
2/3
输入样例 2
5 naboo geonosis yavin hoth endor geonosis yavin hoth endor naboo
输出样例 2
6/10
说明
样例 1 说明:Mirko-wan 凭借元素对 (alpha, beta) 和 (alpha, gamma) 获得了分数。