E. Хязгааргүй солилт

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бүх эерэг тоонуудаас бүрдсэн хязгааргүй өсдөг дараалал байв: $$p = {1, 2, 3, ...}$$

Бид энэ дараалалд $n$ тооны $swap$ үйлдэл хийсэн. $swap(a, b)$ нь дарааллын $a$ ба $b$ байрлалд байгаа элементүүдийг солих үйлдэл юм.

Таны даалгавар бол үүссэн дараалал дахь буурах эрэмбэтэй хосуудын тоог олох юм. Өөрөөр хэлбэл $i < j$ ба $p_{i} > p_{j}$ байх $(i, j)$ хосын тоог хэвлэнэ.

Оролт

Эхний мөрөнд дараалал дээр хийсэн $swap$ үйлдлийн тоо болох $n$ ($1 ≤ n ≤ 10^{5}$) бүхэл тоо байна.

Дараагийн $n$ мөр бүрт солих үйлдлийг илэрхийлэх $a_{i}$ ба $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ 10^{9}$, $a_{i} ≠ b_{i}$) бүхэл тоонууд байна.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Энэ нь үүссэн дарааллын урвуу эрэмбэтэй хосын тоо юм.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
2
4 2
1 4
Гаралт
4
Оролт
3
1 6
3 4
2 5
Гаралт
15

Тэмдэглэл

Эхний жишээнд дараалал дараах байдлаар өөрчлөгдсөн байна:

$(1, 2, 3, 4, 5, ...)$ → $(1, 4, 3, 2, 5, ...)$ → $(2, 4, 3, 1, 5, ...)$

Энд $(1, 4)$, $(2, 3)$, $(2, 4)$, $(3, 4)$ дугааруудтай $4$ урвуу эрэмбэтэй хос байна.

Сэтгэгдлүүдийг ачааллаж байна...