Lista P89562

Mirko ha recibido un regalo de compleaños de su tío en los Estados Unidos – una lista doblemente enlazada (como se muestra en la figura) con los números del 1 al N en orden creciente.

Mirko realiza dos tipos de movimientos en su nueva lista:

• Mover el nodo X justo delante del nodo Y.
• Mover el nodo X justo detrás del nodo Y.

---

Figure 1: Una lista con 6 nodos

---

---

Figure 2: La lista después del movimiento “A 1 4” (colocar el 1 en frente del 4).

---

---

Figure 3: La lista después de otro movimiento, “B 3 5” (colocar el 3 detrás del 5).

---

Mirko ha estado jugando durante horas con su nueva lista, escribiendo en un trozo de papel todos los movimientos que hace. Al acabar, intenta volver a dejar la lista como estaba, deshaciendo sus movimientos. Pero descubre sorprendido que la información que se había guardado no es suficiente para deshacer los movimientos que ha hecho: para cada movimiento, sabe que un nodo acaba de ser puesto detrás (o delante) de otro, pero no sabe dónde estaba antes del movimiento.

Ya que Mirko no puede deshacer todos los pasos que ha hecho, al menos sí puede dejar la lista tal y como estaba. Conociendo los movimientos de Mirko, haz un programa que calcule cuál es el mínimo número de movimientos que es necesario para dejar la lista tal y como estaba.

Entrada

La primera línea contiene dos enteros, N y K (2≤ N≤ 500000, 0≤ M≤ 100000), con el número de nodos y el número de movimientos que ha hecho Mirko.

Cada una de las siguientes M líneas contiene la descripción de un movimiento de Mirko: el tipo (“A” o “B”) y dos enteros X e Y.

Salida

Escribe una línea con el mínimo número de movimientos.