G. Различные числа с изменениями

Дан массив. Запросы двух видов: узнать количество различных значений на отрезке и заменить один элемент массива.

В первой строке $n$ и $q$ ($1 \le n, q \le 5 \cdot 10^4$). Во второй строке $n$ чисел $a_i$ ($1 \le a_i \le 10^6$).

В следующих $q$ строках операции. Операция ? l r ($1 \le l \le r \le n$) — сколько различных значений на отрезке. Операция ! p x ($1 \le p \le n$, $1 \le x \le 10^6$) — присвоить $a_p = x$.

Для каждой операции первого вида выведите ответ в отдельной строке.