eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Инверсии Джона

Инверсии Джона

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

Джон недавно наткнулся на следующее определение инверсии.

Инверсией в последовательности чисел s[k] называется любая пара s[i], s[j] такая что i < j и s[i] > s[j].

Джон полагает, что инверсии являются идеальным инструментом для оценивания того, насколько хорошо последовательность чисел сортируется. Чем меньшее количество инверсий содержится в последовательности, тем лучше она сортируется. Например, если последовательность отсортирована в порядке возрастания, то она содержит ноль инверсий.

Петр дал Джону колоду из n карт. На каждой карте написано два числа - одно красного цвета, другое синего. Джон очень хочет проверить свои знания про инверсии, используя эту колоду.

Он кладет карты перед собой в произвольном порядке и вычисляет общее число хороших инверсий для последовательности чисел, расположенной перед ним. Джон считает инверсию хорошей, если она состоит из номеров одного и того же цвета. В нашем случае хорошая инверсия может быть сформирована либо двумя голубыми, либо двумя красными цифрами. Если количество хороших инверсий слишком велико по меркам Джона, то он перетасовывает карты и повторяет процесс.

Вам следует помочь Джону узнать минимальное возможное количество хороших инверсий следуя по описанному алгоритму.

Входные данные

Первая строка содержит количество карт n (1n100000) в колоде. Каждая из следующих n строк описывает одну карту. i-ая строка содержит два целых числа r[i] и b[i] (1r[i], b[i]10^9), записанные на i-ой карте красным и синим цветов соответственно.

Выходные данные

Вывести минимальное возможное количество хороших инверсий.

Пример

Входные данные #1
3
10 3
20 2
30 1
Выходные данные #1
3
Входные данные #2
4
2 2
5 25
2 1
10 9
Выходные данные #2
1