Олимпиадный тренинг

Задача . F. Машинное обучение

Задача

Вы чувствуете неприятный запах. Откуда же он?

Дан массив a. Вам нужно уметь отвечать на следующие запросы:

Даны целые числа l и r. Пусть c_i — количество вхождений числа i в a_l: r, где a_l: r — это подмассив a с l-го элемента по r-й включительно. Найдите Mex множества {c₀, c₁, ..., c_10⁹}.
Даны целые числа p и x. Присвойте a_p значение x.

Mex мультимножества чисел это минимальное неотрицательное целое число, не входящее в множество.

Обратите внимание, что в данной задаче элементы a положительные, соответственно c₀ = 0, поэтому 0 никогда не является ответом на запрос второго типа.

Входные данные

Первая строка содержит n и q (1 ≤ n, q ≤ 100 000) — размер массива и число запросов соответственно.

Во второй строке записано ровно n чисел — a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹).

Каждая из оставшихся q строк задаёт очередной запрос.

Запрос первого типа задаётся тремя числами t_i = 1, l_i, r_i, где 1 ≤ l_i ≤ r_i ≤ n — границы соответствующего подмассива.

Запрос второго типа задаётся тремя числами t_i = 2, p_i, x_i, где 1 ≤ p_i ≤ n — позиция в которой нужно заменить число, а 1 ≤ x_i ≤ 10⁹ — его новое значение.

Выходные данные

Для каждого запроса первого типа выведите одно число — Mex множества {c₀, c₁, ..., c_10⁹}.

Примечание

Отрезок первого запрос состоит из ровно одного элемента — 1.

Отрезок второго запроса состоит из четырёх 2, одной 3 и двух 1.

Отрезок четвёртого запроса состоит из трёх 1, трёх 2 и одной 3.

Примеры

№	Входные данные	Выходные данные
1	10 4 1 2 3 1 1 2 2 2 9 9 1 1 1 1 2 8 2 7 1 1 2 8	2 3 2

time 4000 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет