Инверсии Джона
Инверсии Джона
Джон недавно наткнулся на следующее определение инверсии.
Инверсией в последовательности чисел sk
называется любая пара si
, sj
такая что i < j и si
> sj
.
Джон полагает, что инверсии являются идеальным инструментом для оценивания того, насколько хорошо последовательность чисел сортируется. Чем меньшее количество инверсий содержится в последовательности, тем лучше она сортируется. Например, если последовательность отсортирована в порядке возрастания, то она содержит ноль инверсий.
Петр дал Джону колоду из n карт. На каждой карте написано два числа - одно красного цвета, другое синего. Джон очень хочет проверить свои знания про инверсии, используя эту колоду.
Он кладет карты перед собой в произвольном порядке и вычисляет общее число *хороших инверсий* для последовательности чисел, расположенной перед ним. Джон считает инверсию хорошей, если она состоит из номеров одного и того же цвета. В нашем случае хорошая инверсия может быть сформирована либо двумя голубыми, либо двумя красными цифрами. Если количество хороших инверсий слишком велико по меркам Джона, то он перетасовывает карты и повторяет процесс.
Вам следует помочь Джону узнать минимальное возможное количество хороших инверсий следуя по описанному алгоритму.
Входные данные
Первая строка содержит количество карт n (1 ≤ n ≤ 100000) в колоде. Каждая из следующих n строк описывает одну карту. i-ая строка содержит два целых числа ri
и bi
(1 ≤ ri
, bi
≤ 109
), записанные на i-ой карте красным и синим цветов соответственно.
Выходные данные
Вывести минимальное возможное количество хороших инверсий.
3 10 3 20 2 30 1
3
4 2 2 5 25 2 1 10 9
1