P5149 Meeting Seats

It is said that the principal has recently been fond of holding all-staff meetings, asking the teachers to attend and listen to his speeches.

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.

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.

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

- 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