Є n кульок у рядку. На i-ій кульці зліва записане число ai.
Можна виконувати операції. За одну операцію виконується наступне:
Нехай k — кількість кульок.
Видаляються усі кульки, на яких записане число k.
Будемо вважати, що рядок кульок можна видалити, якщо після виконання певної кількості операцій, більше не буде жодної кульки.
Також дано m запитів, кожен з яких можна описати двома числами: pi, xi, які означають, що число на pi-ій кульці потрібно замінити на xi. Після кожного такого запиту потрібно знайти мінімальну кількість чисел, які потрібно змінити на кульках, щоб рядок можна було видалити.
Перший рядок містить два цілі числа n та m (1≤n,m≤2⋅105).
Другий рядок містить n цілих чисел a1,a2,…,an (1≤ai≤n).
Кожен з наступних m рядків містить два цілі числа pi та xi (1≤pi,xi≤n).
Виведіть m чисел по одному у рядку.