Battle Order Score

Interview

Time limit1sMemory limit128 MB

Summary
Count pairs of items whose relative order matches between a reference sequence and a given permutation, and print as a fraction over N(N-1)/2.
Level

Medium4 of 10

Topics
Array, Brute force, Sorting
Solved
No attempts yet

Problem

Hyunwoo answered a history test question that asks for several naval battles to be written in chronological order.

The old grading rule compared each position directly with the correct order. Because of that, moving one battle to the wrong end could make an answer receive 0 points even when most pairwise relationships were correct.

The teacher decides to grade the answer again by considering every pair of battles. For each pair, if their relative order in Hyunwoo's answer is the same as their relative order in the correct answer, he earns 1 point. With N battles, there are N(N-1)/2 pairs.

Given the correct order and Hyunwoo's answer, compute Hyunwoo's score.

Input

The first line contains the number of battles N (2 <= N <= 2500).

The next line contains the correct order, separated by spaces. The following line contains Hyunwoo's answer, separated by spaces.

Each battle name consists of 3 to 15 lowercase English letters.

Output

Print Hyunwoo's score in the form a/b. Do not reduce the fraction.

Examples3

  1. Example 1

    Input
    5
okpo sacheon hansan myeongnyang noryang
sacheon hansan myeongnyang noryang okpo
    Expected output
    6/10

  2. Example 2

    Input
    3
alpha beta gamma
alpha gamma beta
    Expected output
    2/3

  3. Example 3

    Input
    5
naboo geonosis yavin hoth endor
geonosis yavin hoth endor naboo
    Expected output
    6/10