Задачі
Инверсии Джона
Инверсии Джона
Джон недавно наткнулся на следующее определение инверсии.
\textit{\textbf{Инверсией}} в последовательности чисел \textbf{s_k} называется любая пара \textbf{s_i}, \textbf{s_j} такая что \textbf{i} < \textbf{j} и \textbf{s_i} > \textbf{s_j}.
Джон полагает, что инверсии являются идеальным инструментом для оценивания того, насколько хорошо последовательность чисел сортируется. Чем меньшее количество инверсий содержится в последовательности, тем лучше она сортируется. Например, если последовательность отсортирована в порядке возрастания, то она содержит ноль инверсий.
Петр дал Джону колоду из \textbf{n} карт. На каждой карте написано два числа - одно красного цвета, другое синего. Джон очень хочет проверить свои знания про инверсии, используя эту колоду.
Он кладет карты перед собой в произвольном порядке и вычисляет общее число \textit{\textbf{хороших инверсий}} для последовательности чисел, расположенной перед ним. Джон считает инверсию хорошей, если она состоит из номеров одного и того же цвета. В нашем случае хорошая инверсия может быть сформирована либо двумя голубыми, либо двумя красными цифрами. Если количество хороших инверсий слишком велико по меркам Джона, то он перетасовывает карты и повторяет процесс.
Вам следует помочь Джону узнать минимальное возможное количество хороших инверсий следуя по описанному алгоритму.
\InputFile
Первая строка содержит количество карт \textbf{n} (\textbf{1 }≤ \textbf{n} ≤ \textbf{100000}) в колоде. Каждая из следующих \textbf{n} строк описывает одну карту. \textbf{i}-ая строка содержит два целых числа \textbf{r_i} и \textbf{b_i} (\textbf{1} ≤ \textbf{r_i}, \textbf{b_i} ≤ \textbf{10^9}), записанные на \textbf{i}-ой карте красным и синим цветов соответственно.
\OutputFile
Вывести минимальное возможное количество хороших инверсий.
Вхідні дані #1
3 10 3 20 2 30 1
Вихідні дані #1
3
Вхідні дані #2
4 2 2 5 25 2 1 10 9
Вихідні дані #2
1