Кульки

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

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

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

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

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

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

Input

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

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

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

Output

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

Examples