Есть бесконечная последовательность, состоящая из всех положительных целых чисел в порядке возрастания: p = {1, 2, 3, ...}. К ней последовательно применили n операций swap. Операция swap(a, b) меняет местами элементы последовательности на позициях a и b. Требуется найти количество инверсий в получившейся последовательности, т.е. количество таких пар индексов (i, j), что i < j и pi > pj.
В первой строке записано единственное целое число n (1 ≤ n ≤ 105) — количество операций swap, примененных к последовательности.
В каждой из следующих n строк записано по два числа ai и bi (1 ≤ ai, bi ≤ 109, ai ≠ bi) — аргументы операций swap.
Выведите единственное целое число — количество инверсий в получившейся последовательности.
В первом примере последовательность меняется следующим образом: . В ней 4 инверсии, их образуют пары индексов (1, 4), (2, 3), (2, 4) и (3, 4).
2 4 2 1 4
4
3 1 6 3 4 2 5
15
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач