Description

The principal posted a seating chart on the campus network: $n$ teachers are arranged in a single row from left to right. The teachers were satisfied with this seating.

However, when the meeting started, the principal accidentally shuffled the seating chart, and the teachers became unhappy. The teachers do not care how much their own positions changed, but if there is a pair of teachers $a$ and $b$ such that in the original seating $a$ was to the left of $b$, and now $a$ is to the right of $b$, then this pair contributes one unit of dissatisfaction.

The principal wants to know the total dissatisfaction value of these teachers.

Input Format

The first line contains a positive integer $n$, the number of teachers.

The second line contains $n$ strings, each being a teacher’s name (case-sensitive). This line represents the original seating chart.

The third line contains $n$ strings, representing the shuffled seating chart.

Output Format

One line containing a non-negative integer, the total dissatisfaction value.

3
Stan Kyle Kenny
Kyle Stan Kenny

1

5
A B C D E
B A D E C

3

Hint

• For $30\%$ of the testdata, $1 \le n \le 10^3$.
• For $100\%$ of the testdata, $1 \le n \le 10^5$, each teacher’s name has length at most $5$, consists only of uppercase and lowercase letters, and all names are distinct. Names are case-sensitive.

Translated by ChatGPT 5