| Codeforces Round 301 (Div. 2) |
|---|
| Закончено |
Есть бесконечная последовательность, состоящая из всех положительных целых чисел в порядке возрастания: 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.
Выведите единственное целое число — количество инверсий в получившейся последовательности.
2
4 2
1 4
4
3
1 6
3 4
2 5
15
В первом примере последовательность меняется следующим образом: 
. В ней 4 инверсии, их образуют пары индексов (1, 4), (2, 3), (2, 4) и (3, 4).
