CF940F.Machine Learning

You come home and fell some unpleasant smell. Where is it coming from?

You are given an array a. You have to answer the following queries:

1. You are given two integers l and r. Let c__i be the number of occurrences of i in a__l: r, where a__l: r is the subarray of a from l-th element to r-th inclusive. Find the Mex of {_c_0, _c_1, ..., _c_109}
2. You are given two integers p to x. Change a__p to x.

The Mex of a multiset of numbers is the smallest non-negative integer not in the set.

Note that in this problem all elements of a are positive, which means that _c_0 = 0 and 0 is never the answer for the query of the second type.

你回到家，闻到一股难闻的气味。它来自哪里？

给你一个数组 $a$。你需要回答以下两类查询：

1. 给定两个整数 $l$ 和 $r$。令 $c_i$ 表示数字 $i$ 在子数组 $a_{l:r}$ 中出现的次数，其中 $a_{l:r}$ 表示数组 $a$ 中从第 $l$ 个元素到第 $r$ 个元素（含端点）构成的子数组。求集合 $\{c_0,\,c_1,\,...,\,c_{10^9}\}$ 的 Mex。
2. 给定两个整数 $p$ 和 $x$，将 $a_p$ 修改为 $x$。

一个多重集（multiset）的 Mex 是该集合中未出现的最小非负整数。

注意：本题中数组 $a$ 的所有元素均为正整数，这意味着 $c_0 = 0$，且对于第二类查询，答案绝不可能是 $0$。

The first line of input contains two integers n and q (1 ≤ n, q ≤ 100 000) — the length of the array and the number of queries respectively.

The second line of input contains n integers — _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109).

Each of the next q lines describes a single query.

The first type of query is described by three integers t__i = 1, l__i, r__i, where 1 ≤ l__i ≤ r__i ≤ n — the bounds of the subarray.

The second type of query is described by three integers t__i = 2, p__i, x__i, where 1 ≤ p__i ≤ n is the index of the element, which must be changed and 1 ≤ x__i ≤ 109 is the new value.

输入的第一行包含两个整数 $n$ 和 $q$（$1 ≤ n, q ≤ 100\,000$），分别表示数组的长度和查询的数量。

输入的第二行包含 $n$ 个整数 — $a_1, a_2, \dots, a_n$（$1 ≤ a_i ≤ 10^9$）。

接下来的 $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^9$ 是该元素的新值。

For each query of the first type output a single integer — the Mex of {_c_0, _c_1, ..., _c_109}.

对于每个第一类查询，输出一个整数——集合 $\{c_0,\,c_1,\,...,\,c_{10^9}\}$ 的 Mex。

The subarray of the first query consists of the single element — 1.

The subarray of the second query consists of four 2s, one 3 and two 1s.

The subarray of the fourth query consists of three 1s, three 2s and one 3.

第一个查询的子数组仅包含单个元素——1。

第二个查询的子数组包含四个 2、一个 3 和两个 1。

第四个查询的子数组包含三个 1、三个 2 和一个 3。