Дек с шариками

Сложность: 55%

Есть шарики, пронумерованные от 11 до nn. Также поступают qq запросов:

  • add x - добавить в дек шарик с номером xx. Вы можете положить шарик либо сверху, либо снизу дека.
  • del x - удалить из дека шарик с номером xx. Вы находите шарик с номером xx в деке, достаете все шарики НИЖЕ xx, удаляете шарик xx, потом кладете достанные шарики (без xx) обратно в том же порядке.

На запросы 11-го типа вы тратите 11 действие, а на запросы 22-го типа - 2k+12k + 1 действий, где kk - количество шариков, которые лежат ниже удаляемого (то есть вы сначала достаете kk шариков, потом удаляете нижний, потом кладете достанные kk шариков обратно в том же порядке).

Посчитайте, какое минимальное количество действий вы можете потратить.

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

Первая строка содержит числа nn и qq (1n,q21051 \leq n, q \leq 2 \cdot 10^5) - максимальный номер шарика и количество запросов. Далее следуют qq строк в формате:

  • add x - добавить шарик с номером xx (1xn1 \leq x \leq n) в начало или конец дека.
  • del x - удалить шарик с номером xx (1xn1 \leq x \leq n) из дека.

Гарантируется, что никакой шарик не добавляется 2 раза, а также, что если есть запрос удаления шарика xx, то он присутствует в деке в данный момент.

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

Выведите единственное число - минимальное количество операций, которое вы можете потратить на запросы.

Подзадачи

баллынеобх. подзадачиограничения
1

15

-

q20q \le 20

2

15

1

В деке всегда не больше 6 элементов, q1000q \le 1000

3

10

2

В деке всегда не больше 10 элементов, q1000q \le 1000

4

25

3

qn106q \cdot n \le 10^6

5

5

3

q5000q \le 5000

6

30

4, 5

Нет дополнительных ограничений

STDINSTDOUT
2 4
add 1
del 1
add 2
del 2
4
8 6
add 5
add 8
del 5
add 1
add 4
del 1
6