Кульки#12820

Кульки

Є кульок у рядку. На -ій кульці зліва записане число a_i.

Можна виконувати операції. За одну операцію виконується наступне:

  1. Нехай  — кількість кульок.

  2. Видаляються усі кульки, на яких записане число .

Будемо вважати, що рядок кульок можна видалити, якщо після виконання певної кількості операцій, більше не буде жодної кульки.

Також дано запитів, кожен з яких можна описати двома числами: p_i, x_i, які означають, що число на p_i-ій кульці потрібно замінити на x_i. Після кожного такого запиту потрібно знайти мінімальну кількість чисел, які потрібно змінити на кульках, щоб рядок можна було видалити.

Вхідні дані

Перший рядок містить два цілі числа та (1 \leq n, m \leq 2 \cdot 10^5).

Другий рядок містить цілих чисел a_1, a_2, \dots, a_n (1 \leq a_i \leq n).

Кожен з наступних рядків містить два цілі числа p_i та x_i (1 \leq p_i, x_i \leq n).

Вихідні дані

Виведіть чисел по одному у рядку.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading