## USACO 2017 February Contest, Gold

## Problem 3. Why Did the Cow Cross the Road III

Contest has ended.

**Log in to allow submissions in analysis mode**

As we know, cows are creatures of habit, and they each cross the road the same way every day. Each cow crosses into the field at a different point from where she crosses out of the field, and all of these crossing points are distinct from each-other. Farmer John owns $N$ cows, conveniently identified with the integer IDs $1 \ldots N$, so there are precisely $2N$ crossing points around the road. Farmer John records these crossing points concisely by scanning around the circle clockwise, writing down the ID of the cow for each crossing point, ultimately forming a sequence with $2N$ numbers in which each number appears exactly twice. He does not record which crossing points are entry points and which are exit points.

Looking at his map of crossing points, Farmer John is curious how many times various pairs of cows might cross paths during the day. He calls a pair of cows $(a,b)$ a "crossing" pair if cow $a$'s path from entry to exit must cross cow $b$'s path from entry to exit. Please help Farmer John count the total number of crossing pairs.

#### INPUT FORMAT (file circlecross.in):

The first line of input contains $N$ ($1 \leq N \leq 50,000$), and the next $2N$ lines describe the cow IDs for the sequence of entry and exit points around the field.#### OUTPUT FORMAT (file circlecross.out):

Please print the total number of crossing pairs.#### SAMPLE INPUT:

4 3 2 4 4 1 3 2 1

#### SAMPLE OUTPUT:

3

Problem credits: Brian Dean