Ферма Джона имеет большую круглую дорогу по периметру главного поля, на котором
его коровы пасутся каждый день. Каждое утро коровы переходят через эту дорогу,
идя в поле, а каждый вечер переходят дорогу ещё раз, возвращаясь в амбар.
Как известно, коровы - существа привычки, поэтому они переходят дорогу
одним и тем же способом каждый день. Каждая корова приходит в поле в точке,
отличающейся от той, в которой она с него уходит, и все эти точки для разных
коров также отличаются друг от друга. У ФД есть \(N\) коров, последовательно
пронумерованных \(1 \ldots N\), Поэтому имеется ровно \(2N\) точек у дороги.
ФД выписал все эти точки по номерам коров, по часовой стрелке, сформировав
последовательность из \(2N\) чисел, каждое из которых встречается в этой
последовательности ровно дважды. Он не записывал, является ли эта точка точкой
входа или точкой выхода.
По его карте точек ФД хочет узнать, сколько путей различных пар коров могут
пересечься в течение дня. Он называет пару коров \((a,b)\) пересекающейся парой,
если путь коровы \(a\) от входа к выходу должен пересечься с путём коровы \(b\)
от входа к выходу. Помогите ФД вычислить общее количество пересекающихся пар.
ФОРМАТ ВВОДА (файл circlecross.in):
Первая строка ввода содержит \(N\) (\(1 \leq N \leq 50,000\)), а последующие \(2N\)
строк описывают номера коров в последовательности входов и выходов вокруг поля.
ФОРМАТ ВЫВОДА (файл circlecross.out):
Выведите количество пересекающихся пар.
| № | Входные данные | Выходные данные |
|
1
|
4
3
2
4
4
1
3
2
1
|
3
|