Lowland Distance (APCS 2020-10 Expert)

Problem Description

An alien archaeology team found an ancient site with \(2n\) fortresses in a row. They further discovered that fortress heights appear in pairs: each height appears in exactly two fortresses. For every pair of fortresses with the same height, the team defines the "lowland distance" of this pair as the number of fortresses between them whose heights are lower. The team wants to compute the total lowland distance of all these fortresses. Please design a program to help calculate it.

More precisely, suppose the sequence of fortress heights from left to right is \((h_1,h_2,\ldots,h_{2n})\), where every height from \(1\) to \(n\) appears exactly twice. For \(1 \le k \le n\), the lowland distance of the fortresses with height \(k\) is

where \(h_p=h_q=k\).

This problem asks you to compute \(\sum_{k=1}^{n} d(k)\).

For example, when \(n = 4\) and the fortress heights are \((1,4,3,2,3,1,2,4)\), heights \(1\), \(2\), \(3\), and \(4\) each appear twice. By definition, the lowland distance of height \(1\) is \(0\), because there is no number smaller than \(1\) between the two $1$s. The lowland distance of height \(2\) is \(1\), because there is only one \(1\) between the two $2$s, and it is smaller than \(2\). Similarly, the lowland distance of height \(3\) is also \(1\), while the lowland distance of height \(4\) is \(5\). Therefore, the total lowland distance is \(0 + 1 + 1 + 5 = 7\).

Hint: this problem has multiple solutions. One solution separates the height sequence into two subsequences by height, then recursively solves it with divide and conquer. Another solution computes, for each position \(i\), the number of fortresses before \(i\) whose heights are smaller than \(h_i\).

Input

The first line contains \(n\), meaning there are \(2n\) fortresses in total, and \(n\) does not exceed \(10^5\). The second line contains \(2n\) positive integers, giving the heights of the fortresses from left to right. Each height is at most \(n\), and adjacent numbers on the same line are separated by spaces. The input guarantees that equal heights appear exactly twice; that is, every integer from \(1\) to \(n\) appears exactly twice.

Output

Output the total lowland distance of all heights. Note that the answer may exceed \(2^{31}\).

Sample Input 1

4
1 4 3 2 3 1 2 4

Sample Output 1

7

Sample Input 2

5
1 2 3 4 4 3 2 1 5 5

Sample Output 2

0

Scoring

The input contains several test cases. For each test case, Python programs have a time limit of 3 seconds, and programs in other languages have a time limit of 1 second. Scores are awarded according to the number of correctly passed test cases:

Subtask group 1: 20 points, \(n\) does not exceed \(1000\).

Subtask group 2: 40 points, \(n\) does not exceed \(40000\).

Subtask group 3: 40 points, no additional constraints.

Source

Source: Programming Implementation, October 2020.