E. Антон и перестановка
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Антон обожает перестановки. Особенно ему нравится переставлять в них элементы местами. Напомним, что перестановкой из n элементов называется последовательность из чисел {a1, a2, ..., an}, в которой каждое из чисел от 1 до n встречается ровно по одному разу.

Однажды Антон получил новую перестановку и начал с ней играть. Он q раз делал следующую операцию: брал какие-то два элемента перестановки и менял их местами. После каждой операции он спрашивал своего друга Ваню: а сколько же инверсий в новой перестановке? Количеством инверсий в перестановке называется количество различных пар (i, j), таких, что 1 ≤ i < j ≤ n и ai > aj.

Ване надоело отвечать на глупые вопросы Антона и он попросил Вас написать программу, которая будет отвечать на эти вопросы за него.

Изначально перестановка Антона имела вид {1, 2, ..., n}, то есть ai = i для всех i таких, что 1 ≤ i ≤ n.

Входные данные

В первой строке входных данных находятся целые числа n и q (1 ≤ n ≤ 200 000, 1 ≤ q ≤ 50 000) — длина перестановки и количество операций, которые сделал Антон.

В каждой из следующих q строк находятся целые числа li и ri (1 ≤ li, ri ≤ n) — номера элементов, которые поменял местами Антон в ходе i-й операции. Обратите внимание, что позиции элементов, которые поменял местами Антон в ходе i-й операции могут совпадать. Элементы в перестановке нумеруются, начиная с единицы.

Выходные данные

Выведите q целых чисел, по одному числу в каждой строке — ответы на глупые вопросы Антона. i-е число в выходных данных должно обозначать количество инверсий в перестановке после выполнения i-й операции.

Примеры
Входные данные
5 4
4 5
2 4
2 5
2 2
Выходные данные
1
4
3
3
Входные данные
2 1
2 1
Выходные данные
1
Входные данные
6 7
1 4
3 5
2 3
3 3
3 6
2 1
5 1
Выходные данные
5
6
7
7
10
11
8
Примечание

Рассмотрим первый пример.

После первой операции Антона перестановка будет иметь вид {1, 2, 3, 5, 4}. В ней всего одна инверсия: (4, 5).

После второй операции Антона перестановка будет иметь вид {1, 5, 3, 2, 4}. В ней четыре инверсии: (2, 3), (2, 4), (2, 5) и (3, 4).

После третьей операции Антона перестановка будет иметь вид {1, 4, 3, 2, 5}. В ней три инверсии: (2, 3), (2, 4) и (3, 4).

После четвертой операции Антона перестановка не меняется. В ней по-прежнему остается три инверсии.