Інверсії Джона
Джон нещодавно дізнався про таке поняття, як інверсія.
Інверсія в послідовності чисел s[k] — це будь-яка пара s[i], s[j], для якої i < j і s[i] > s[j].
Джон вважає, що інверсії є чудовим інструментом для оцінки ступеня відсортованості числової послідовності. Чим менше інверсій у послідовності, тим краще вона відсортована. Наприклад, якщо послідовність відсортована за зростанням, то вона не містить жодної інверсії.
Петро дав Джону колоду з n карт. На кожній карті написано два числа: одне червоного кольору, інше синього. Джон хоче перевірити свої знання про інверсії, використовуючи цю колоду.
Він розкладає карти перед собою в довільному порядку і обчислює загальну кількість хороших інверсій у послідовності чисел, що лежать перед ним. Джон вважає інверсію хорошою, якщо вона складається з чисел одного кольору. У нашому випадку хороша інверсія може бути утворена або двома синіми, або двома червоними числами. Якщо кількість хороших інверсій здається Джону занадто великою, він перетасовує карти і повторює процес.
Вам потрібно допомогти Джону визначити мінімальну можливу кількість хороших інверсій, дотримуючись описаного алгоритму.
Вхідні дані
Перший рядок містить кількість карт n (1 ≤ n ≤ 100000) у колоді. Кожен з наступних n рядків описує одну карту. i-ий рядок містить два цілі числа r[i] і b[i] (1 ≤ r[i], b[i] ≤ 10^9), записані на i-ій карті червоним і синім кольорами відповідно.
Вихідні дані
Виведіть мінімальну можливу кількість хороших інверсій.