eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Динамическая инверсия

Динамическая инверсия

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Задана перестановка {1, 2, 3, ..., n}. Удалите из нее m элементов один за одним, и выведите количество пар инверсий перед каждым удалением. Количество пар инверсий в массиве a равно числу упорядоченных пар (i, j) таких что i < j и a[i] > a[j].

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

Состоит из нескольких тестов. Первая строка каждого теста содержит два целых числа n и m (1n2 * 10^5, 1m10^5). Далее n строк задают начальную перестановку. Следующие m строк задают удаляемые числа в порядке их удаления. Ни одно число не удаляется дважды.

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

Для каждого удаления вывести количество пар инверсий перед ним.

Пример

(1, 5, 3, 4, 2) -> (1, 3, 4, 2) -> (3, 4, 2) -> (3, 2) -> (3)

Пример

Входные данные #1
5 4
1
5
3
4
2
5
1
4
2
Выходные данные #1
5
2
2
1