Антон обожает перестановки. Особенно ему нравится переставлять в них элементы местами. Напомним, что перестановкой из n элементов называется последовательность из чисел {a1, a2, ..., an}, в которой каждое из чисел от 1 до n встречается ровно по одному разу.
Однажды Антон получил новую перестановку и начал с ней играть. Он q раз делал следующую операцию: брал какие-то два элемента перестановки и менял их местами. После каждой операции он спрашивал своего друга Ваню: а сколько же инверсий в новой перестановке? Количеством инверсий в перестановке называется количество различных пар (i, j), таких, что 1 ≤ i < j ≤ n и ai > aj.
Ване надоело отвечать на глупые вопросы Антона и он попросил Вас написать программу, которая будет отвечать на эти вопросы за него.
Изначально перестановка Антона имела вид {1, 2, ..., n}, то есть ai = i для всех i таких, что 1 ≤ i ≤ n.
Выходные данные
Выведите q целых чисел, по одному числу в каждой строке — ответы на глупые вопросы Антона. i-е число в выходных данных должно обозначать количество инверсий в перестановке после выполнения i-й операции.
Примечание
Рассмотрим первый пример.
После первой операции Антона перестановка будет иметь вид {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).
После четвертой операции Антона перестановка не меняется. В ней по-прежнему остается три инверсии.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
4 5
2 4
2 5
2 2
|
1
4
3
3
|
|
2
|
2 1
2 1
|
1
|
|
3
|
6 7
1 4
3 5
2 3
3 3
3 6
2 1
5 1
|
5
6
7
7
10
11
8
|