Почему корова перешла дорогу III (Золото)
Ферма Джона имеет большую круглую дорогу по периметру главного поля, на котором его коровы пасутся каждый день. Каждое утро коровы переходят через эту дорогу, идя в поле, а каждый вечер переходят дорогу ещё раз, возвращаясь в амбар.
Как известно, коровы - существа привычки, поэтому они переходят дорогу одним и тем же способом каждый день. Каждая корова приходит в поле в точке, отличающейся от той, в которой она с него уходит, и все эти точки для разных коров также отличаются друг от друга. У ФД есть n коров, последовательно пронумерованных 1 .. n, Поэтому имеется ровно 2n точек у дороги. ФД выписал все эти точки по номерам коров, по часовой стрелке, сформировав последовательность из 2n чисел, каждое из которых встречается в этой последовательности ровно дважды. Он не записывал, является ли эта точка точкой входа или точкой выхода.
По его карте точек ФД хочет узнать, сколько путей различных пар коров могут пересечься в течение дня. Он называет пару коров (a, b) пересекающейся парой, если путь коровы a от входа к выходу должен пересечься с путём коровы b от входа к выходу. Помогите ФД вычислить общее количество пересекающихся пар.
Входные данные
Первая строка содержит n (1 ≤ n ≤ 50000), а последующие 2n строк описывают номера коров в последовательности входов и выходов вокруг поля.
Выходные данные
Выведите количество пересекающихся пар.