Інверсії Джона#2379

Інверсії Джона

1 секунда

256 мегабайтів

Дуже легка

Джон нещодавно дізнався про визначення інверсії.

Інверсія у послідовності чисел $s_{k}$ s_k — це будь-яка пара $s_{i}, s_{j}$ s_i,\ s_j, така що $i < j$ i < j та $s_{i} > s_{j}$ s_i > s_j.

Джон вважає, що інверсії — це ідеальний інструмент для оцінки того, наскільки добре впорядкована послідовність чисел. Чим менше інверсій у послідовності, тим краще вона впорядкована. Наприклад, якщо послідовність впорядкована за зростанням, то в ній нуль інверсій.

Петро дав Джону колоду з $n$ карт. На кожній карті написано два числа: одне червоним, інше синім. Джон хоче використати цю колоду, щоб застосувати свої знання про інверсії.

Він розкладає карти перед собою у довільному порядку й підраховує загальну кількість гарних інверсій у отриманих послідовностях чисел. Джон вважає інверсію гарною, якщо вона складається з чисел одного кольору. У цьому випадку гарна інверсія може бути утворена або двома синіми, або двома червоними числами. Якщо кількість гарних інверсій, на думку Джона, занадто велика, він тасує карти й повторює процес.

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

Вхідні дані

Перший рядок містить одне ціле число $n$ ( $1 \leq n \leq 100000$ 1 \leq n \leq 100000) — кількість карт у колоді. Кожен з наступних $n$ рядків описує одну карту. $i$ -й рядок містить два цілих числа $r_{i}$ r_i і $b_{i}$ b_i ( $1 \leq r_{i}, b_{i} \leq 1 0^{9}$ 1 \leq r_i, b_i \leq 10^9) — числа, написані на $i$ -й карті червоним і синім відповідно.

Вихідні дані

Виведіть мінімальну можливу кількість гарних інверсій.

Приклади

Приклад 1

Приклад 2