Why Did the Cow Cross the Road 9

Interview

Time limit2sMemory limit512 MB

Summary

Given a circular sequence where each cow label appears exactly twice, count pairs of cows whose chords necessarily cross.

Level: Medium6 of 10
Topics: Array, Hash map, Divide and conquer, Sorting
Solved: No attempts yet

Problem

This story takes place before John reorganized his farm.

John's farm has a circular pasture, and a road runs around its boundary. Every morning John's cows cross this road to graze in the pasture, and every evening they cross it again to return to the barn.

Out of habit, the cows cross the road the same way every day. Each cow enters through one fixed point on the circular road and leaves through a different point. No two cows pass through the same point on the road. John watched this and decided to analyze these points. There are $N$ cows in total, numbered $1, 2, \ldots, N$ . (The cows used to be named A through Z, but that scheme stopped working once the herd grew.) John walked clockwise around the $2N$ points and recorded which cow passes through each point. In the resulting sequence of length $2N$ , every number appears exactly twice.

For some pairs of cows, the two paths must meet somewhere no matter how the cows walk. Find the number of such pairs.

Input

The first line contains $N$ $(1 \le N \le 50\,000)$ . Each of the next $2N$ lines contains the number of the cow that passes through a point on the road, listing the points in clockwise order. Every number from $1$ to $N$ appears exactly twice.

Output

Print the number of pairs of cows whose paths must meet.

Examples1

Example 1
Input
```
4
3
2
4
4
1
3
2
1
```
Expected output
```
3
```