{"raw_statement":[{"iden":"statement","content":"_You come home and fell some unpleasant smell. Where is it coming from?_\n\nYou are given an array _a_. You have to answer the following queries:\n\n1.  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}\n2.  You are given two integers _p_ to _x_. Change _a__p_ to _x_.\n\nThe **Mex** of a multiset of numbers is the smallest non-negative integer **not in** the set.\n\nNote 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."},{"iden":"input","content":"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.\n\nThe second line of input contains _n_ integers — _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109).\n\nEach of the next _q_ lines describes a single query.\n\nThe 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.\n\nThe 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."},{"iden":"output","content":"For each query of the first type output a single integer — the **Mex** of {_c_0, _c_1, ..., _c_109}."},{"iden":"example","content":"Input\n\n10 4\n1 2 3 1 1 2 2 2 9 9\n1 1 1\n1 2 8\n2 7 1\n1 2 8\n\nOutput\n\n2\n3\n2"},{"iden":"note","content":"The subarray of the first query consists of the single element — 1.\n\nThe subarray of the second query consists of four 2s, one 3 and two 1s.\n\nThe subarray of the fourth query consists of three 1s, three 2s and one 3."}],"translated_statement":[{"iden":"statement","content":"_你回到家，闻到一股难闻的气味。它从哪里来的？_\n\n给你一个数组 #cf_span[a]。你需要回答以下查询：\n\n一个多重集合的 *Mex* 是不在该集合中的最小非负整数。\n\n注意，在本题中，数组 #cf_span[a] 的所有元素均为正数，这意味着 #cf_span[c0] = 0，且对于第二类查询，#cf_span[0] 永远不会是答案。\n\n输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[q] (#cf_span[1 ≤ n, q ≤ 100 000]) —— 分别表示数组长度和查询数量。\n\n第二行包含 #cf_span[n] 个整数 —— #cf_span[a1], #cf_span[a2], #cf_span[...], #cf_span[an] (#cf_span[1 ≤ ai ≤ 109])。\n\n接下来的 #cf_span[q] 行每行描述一个查询。\n\n第一类查询由三个整数 #cf_span[ti = 1], #cf_span[li], #cf_span[ri] 描述，其中 #cf_span[1 ≤ li ≤ ri ≤ n] —— 子数组的边界。\n\n第二类查询由三个整数 #cf_span[ti = 2], #cf_span[pi], #cf_span[xi] 描述，其中 #cf_span[1 ≤ pi ≤ n] 是待修改元素的索引，#cf_span[1 ≤ xi ≤ 109] 是新值。\n\n对于每个第一类查询，输出一个整数 —— #cf_span[{c0, c1, ..., c109}] 的 *Mex*。\n\n第一个查询的子数组仅包含一个元素 —— #cf_span[1]。\n\n第二个查询的子数组包含四个 #cf_span[2]、一个 #cf_span[3] 和两个 #cf_span[1]。\n\n第四个查询的子数组包含三个 #cf_span[1]、三个 #cf_span[2] 和一个 #cf_span[3]。\n\n"},{"iden":"input","content":"输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[q] (#cf_span[1 ≤ n, q ≤ 100 000]) —— 分别表示数组长度和查询数量。第二行包含 #cf_span[n] 个整数 —— #cf_span[a1], #cf_span[a2], #cf_span[...], #cf_span[an] (#cf_span[1 ≤ ai ≤ 109])。接下来的 #cf_span[q] 行每行描述一个查询。第一类查询由三个整数 #cf_span[ti = 1], #cf_span[li], #cf_span[ri] 描述，其中 #cf_span[1 ≤ li ≤ ri ≤ n] —— 子数组的边界。第二类查询由三个整数 #cf_span[ti = 2], #cf_span[pi], #cf_span[xi] 描述，其中 #cf_span[1 ≤ pi ≤ n] 是待修改元素的索引，#cf_span[1 ≤ xi ≤ 109] 是新值。"},{"iden":"output","content":"对于每个第一类查询，输出一个整数 —— #cf_span[{c0, c1, ..., c109}] 的 *Mex*。"},{"iden":"note","content":"第一个查询的子数组仅包含一个元素 —— #cf_span[1]。第二个查询的子数组包含四个 #cf_span[2]、一个 #cf_span[3] 和两个 #cf_span[1]。第四个查询的子数组包含三个 #cf_span[1]、三个 #cf_span[2] 和一个 #cf_span[3]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, q \\in \\mathbb{Z}^+ $ denote the length of the array and number of queries, respectively.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be an array of positive integers, where $ a_i \\in [1, 10^9] $.  \n\n**Constraints**  \n1. $ 1 \\leq n, q \\leq 100{,}000 $  \n2. $ 1 \\leq a_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. For each query:  \n   - Type 1: $ t_i = 1 $, $ 1 \\leq l_i \\leq r_i \\leq n $ — query Mex over subarray $ A[l_i:r_i] $  \n   - Type 2: $ t_i = 2 $, $ 1 \\leq p_i \\leq n $, $ 1 \\leq x_i \\leq 10^9 $ — update $ a_{p_i} \\gets x_i $  \n\n**Objective**  \nFor each query of type 1, compute the **Mex** of the multiset $ S = \\{ a_j \\mid l_i \\leq j \\leq r_i \\} $, defined as:  \n$$\n\\mathrm{Mex}(S) = \\min \\left( \\mathbb{Z}_{\\geq 0} \\setminus S \\right)\n$$  \n(Note: Since all $ a_i \\geq 1 $, $ 0 \\notin S $, so $ \\mathrm{Mex}(S) = 0 $ if $ 0 \\notin S $, otherwise the smallest missing non-negative integer.)","simple_statement":null,"has_page_source":false}