Our friends at Bitdefender want to develop a newer, better, faster, stronger antivirus program. They realized that the software works best if all 2*N computers in the network are arranged in a circle, and each computer is tied to exactly one other peer with a straight cable. Each pair of computers tied together is associated a unique ID, for the sake of simplicity.

This layout is encoded as 2*N integers: the IDs of each computer you encounter if you start at some point on the circle and traverse it in clockwise order once. Naturally, each value between 1 and N will occur twice (once for each endpoint of a connected pair of computers).

Due to the physical arrangement of the computers, the engineers noticed that some of the cables intersect each other. Now they are wondering whether or not it is possible to compute how many pairs of intersecting cables there are, based on a given layout.


The first line of input contains N - the number of cables.
The second line of input contains 2*N integers - the network layout.


A single integer: the number of overlapping pairs of cables.


  • 1 ≤ N ≤ 50 000


1 2 3 2 3 1
1 The only segments that intersect are 2 and 3.

Sponsors Gold