{"raw_statement":[{"iden":"statement","content":"Initially there was an array $a$ consisting of $n$ integers. Positions in it are numbered from $1$ to $n$.\n\nExactly $q$ queries were performed on the array. During the $i$\\-th query some segment $(l_i, r_i)$ $(1 \\le l_i \\le r_i \\le n)$ was selected and values of elements on positions from $l_i$ to $r_i$ inclusive got changed to $i$. The order of the queries couldn't be changed and all $q$ queries were applied. It is also known that every position from $1$ to $n$ got covered by at least one segment.\n\nWe could have offered you the problem about checking if some given array (consisting of $n$ integers with values from $1$ to $q$) can be obtained by the aforementioned queries. However, we decided that it will come too easy for you.\n\nSo the enhancement we introduced to it is the following. Some set of positions (possibly empty) in this array is selected and values of elements on these positions are set to $0$.\n\nYour task is to check if this array can be obtained by the aforementioned queries. Also if it can be obtained then restore this array.\n\nIf there are multiple possible arrays then print any of them."},{"iden":"input","content":"The first line contains two integers $n$ and $q$ ($1 \\le n, q \\le 2 \\cdot 10^5$) — the number of elements of the array and the number of queries perfomed on it.\n\nThe second line contains $n$ integer numbers $a_1, a_2, \\dots, a_n$ ($0 \\le a_i \\le q$) — the resulting array. If element at some position $j$ is equal to $0$ then the value of element at this position can be any integer from $1$ to $q$."},{"iden":"output","content":"Print \"_YES_\" if the array $a$ can be obtained by performing $q$ queries. Segments $(l_i, r_i)$ $(1 \\le l_i \\le r_i \\le n)$ are chosen separately for each query. Every position from $1$ to $n$ should be covered by at least one segment.\n\nOtherwise print \"_NO_\".\n\nIf some array can be obtained then print $n$ integers on the second line — the $i$\\-th number should be equal to the $i$\\-th element of the resulting array and should have value from $1$ to $q$. This array should be obtainable by performing exactly $q$ queries.\n\nIf there are multiple possible arrays then print any of them."},{"iden":"examples","content":"Input\n\n4 3\n1 0 2 3\n\nOutput\n\nYES\n1 2 2 3\n\nInput\n\n3 10\n10 10 10\n\nOutput\n\nYES\n10 10 10 \n\nInput\n\n5 6\n6 5 6 2 2\n\nOutput\n\nNO\n\nInput\n\n3 5\n0 0 0\n\nOutput\n\nYES\n5 4 2"},{"iden":"note","content":"In the first example you can also replace $0$ with $1$ but not with $3$.\n\nIn the second example it doesn't really matter what segments to choose until query $10$ when the segment is $(1, 3)$.\n\nThe third example showcases the fact that the order of queries can't be changed, you can't firstly set $(1, 3)$ to $6$ and after that change $(2, 2)$ to $5$. The segment of $5$ should be applied before segment of $6$.\n\nThere is a lot of correct resulting arrays for the fourth example."}],"translated_statement":[{"iden":"statement","content":"最初有一个包含 $n$ 个整数的数组 $a$，其位置编号从 $1$ 到 $n$。\n\n对该数组执行了恰好 $q$ 次查询。在第 $i$ 次查询中，选择了一个区间 $(l_i, r_i)$（满足 $1 lt.eq l_i lt.eq r_i lt.eq n$），并将位置从 $l_i$ 到 $r_i$（含）的所有元素的值更改为 $i$。查询的顺序不可更改，且所有 $q$ 次查询均被应用。同时已知，从 $1$ 到 $n$ 的每个位置至少被一个区间覆盖。\n\n我们本可以向你提出一个问题：检查某个给定数组（由 $n$ 个取值在 $1$ 到 $q$ 之间的整数组成）是否可以通过上述查询得到。但我们决定这对你来说太简单了。\n\n因此，我们对此问题进行了增强：在该数组中选择了一个位置集合（可能为空），并将这些位置上的元素值设为 $0$。\n\n你的任务是判断该数组是否可以通过上述查询得到。如果可以，请还原该数组。\n\n如果有多个可能的数组，请输出其中任意一个。\n\n第一行包含两个整数 $n$ 和 $q$（$1 lt.eq n, q lt.eq 2 dot.op 10^5$）——数组的元素个数和对其执行的查询次数。\n\n第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$（$0 lt.eq a_i lt.eq q$）——最终的数组。如果某个位置 $j$ 的元素等于 $0$，则该位置的值可以是 $1$ 到 $q$ 之间的任意整数。\n\n如果数组 $a$ 可以通过执行 $q$ 次查询得到，则输出 \"_YES_\"。每个查询选择的区间 $(l_i, r_i)$（$1 lt.eq l_i lt.eq r_i lt.eq n$）彼此独立，且从 $1$ 到 $n$ 的每个位置都必须至少被一个区间覆盖。\n\n否则输出 \"_NO_\"。\n\n如果可以得到某个数组，则在第二行输出 $n$ 个整数——第 $i$ 个数应等于结果数组中第 $i$ 个元素的值，且必须在 $1$ 到 $q$ 之间。该数组必须可通过恰好执行 $q$ 次查询得到。\n\n如果有多个可能的数组，请输出其中任意一个。\n\n在第一个示例中，你可以将 $0$ 替换为 $1$，但不能替换为 $3$。\n\n在第二个示例中，在第 $10$ 次查询之前，选择什么区间并不重要，此时区间为 $(1, 3)$。\n\n第三个示例展示了查询顺序不可更改的事实：你不能先将 $(1, 3)$ 设为 $6$，然后再将 $(2, 2)$ 设为 $5$。$5$ 的区间必须在 $6$ 的区间之前应用。\n\n第四个示例中有许多正确的结果数组。"},{"iden":"input","content":"第一行包含两个整数 $n$ 和 $q$（$1 lt.eq n, q lt.eq 2 dot.op 10^5$）——数组的元素个数和对其执行的查询次数。第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$（$0 lt.eq a_i lt.eq q$）——最终的数组。如果某个位置 $j$ 的元素等于 $0$，则该位置的值可以是 $1$ 到 $q$ 之间的任意整数。"},{"iden":"output","content":"如果数组 $a$ 可以通过执行 $q$ 次查询得到，则输出 \"_YES_\"。每个查询选择的区间 $(l_i, r_i)$（$1 lt.eq l_i lt.eq r_i lt.eq n$）彼此独立，且从 $1$ 到 $n$ 的每个位置都必须至少被一个区间覆盖。否则输出 \"_NO_\"。如果可以得到某个数组，则在第二行输出 $n$ 个整数——第 $i$ 个数应等于结果数组中第 $i$ 个元素的值，且必须在 $1$ 到 $q$ 之间。该数组必须可通过恰好执行 $q$ 次查询得到。如果有多个可能的数组，请输出其中任意一个。"},{"iden":"examples","content":"输入\n4 3\n1 0 2 3\n输出\nYES\n1 2 2 3\n\n输入\n3 10\n10 10 10\n输出\nYES\n10 10 10\n\n输入\n5 6\n6 5 6 2 2\n输出\nNO\n\n输入\n3 5\n0 0 0\n输出\nYES\n5 4 2"},{"iden":"note","content":"在第一个示例中，你可以将 $0$ 替换为 $1$，但不能替换为 $3$。在第二个示例中，在第 $10$ 次查询之前，选择什么区间并不重要，此时区间为 $(1, 3)$。第三个示例展示了查询顺序不可更改的事实：你不能先将 $(1, 3)$ 设为 $6$，然后再将 $(2, 2)$ 设为 $5$。$5$ 的区间必须在 $6$ 的区间之前应用。第四个示例中有许多正确的结果数组。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, q \\in \\mathbb{Z}^+ $ denote the length of the array and the number of queries.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the given array, where $ a_i \\in \\{0, 1, 2, \\dots, q\\} $.  \nLet $ S = \\{ i \\in \\{1, \\dots, n\\} \\mid a_i = 0 \\} $ be the set of positions with unknown (zero) values.  \n\nFor each query $ i \\in \\{1, \\dots, q\\} $, there exists a segment $ [l_i, r_i] \\subseteq [1, n] $ such that all positions in $ [l_i, r_i] $ are assigned value $ i $ during the $ i $-th query.  \nQueries are applied sequentially in order $ 1 $ to $ q $, and each position $ j \\in [1, n] $ must be covered by at least one segment.  \n\n**Constraints**  \n1. $ 1 \\leq n, q \\leq 2 \\cdot 10^5 $  \n2. $ 0 \\leq a_i \\leq q $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. Every position $ j \\in \\{1, \\dots, n\\} $ is covered by at least one query segment.  \n4. For any two queries $ i < j $, if position $ k $ is covered by both $ [l_i, r_i] $ and $ [l_j, r_j] $, then the final value at $ k $ is $ j $ (due to sequential overwrite).  \n\n**Objective**  \nDetermine whether there exists an assignment $ b = (b_1, \\dots, b_n) $ such that:  \n- $ b_i = a_i $ for all $ i \\notin S $,  \n- $ b_i \\in \\{1, \\dots, q\\} $ for all $ i \\in S $,  \n- There exist segments $ [l_1, r_1], \\dots, [l_q, r_q] $ such that applying queries $ 1 $ to $ q $ in order yields $ b $.  \n\nAdditionally, if such $ b $ exists, output any valid $ b $.  \n\n**Key Necessary Conditions**  \nLet $ f(j) $ be the final value at position $ j $ (i.e., $ b_j $).  \nThen:  \n- For each $ i \\in \\{1, \\dots, q\\} $, the set $ \\{ j \\mid f(j) = i \\} $ must form a contiguous interval.  \n- If $ i < j $ and both $ f(k_1) = i $, $ f(k_2) = j $, and $ f(k_3) = i $ for some $ k_1 < k_2 < k_3 $, then the assignment is invalid (since query $ j $ would overwrite $ i $ in between, preventing $ i $ from appearing again later).  \n- For each $ i \\in \\{1, \\dots, q\\} $, if $ i $ appears in $ b $, then all occurrences of $ i $ must be contiguous, and no larger-indexed query value may appear *between* two occurrences of $ i $.  \n- The maximum value appearing in $ b $ must be $ q $, and it must appear in at least one position.  \n- For each $ i \\in \\{1, \\dots, q\\} $, define $ L_i = \\min\\{ j \\mid b_j = i \\} $, $ R_i = \\max\\{ j \\mid b_j = i \\} $. Then $ [L_i, R_i] \\subseteq [L_{i+1}, R_{i+1}] $ is **not** required, but if $ L_j < L_i < R_j $ for some $ j > i $, then $ R_i $ must be $ \\leq R_j $, and no position between $ L_i $ and $ R_i $ may have a value $ > i $ unless it is overwritten by $ j > i $.  \n\n**Reconstruction Strategy (Implicit)**  \n- For each $ i \\in \\{1, \\dots, q\\} $, define $ \\text{first}_i = \\min \\{ j \\mid a_j = i \\} $, $ \\text{last}_i = \\max \\{ j \\mid a_j = i \\} $ (if none, then $ \\text{first}_i = \\text{last}_i = \\infty $).  \n- For each zero position $ j $, assign it the value of the **last** query $ i $ such that $ \\text{first}_i \\leq j \\leq \\text{last}_i $ and $ i $ is maximal among such queries. If no such $ i $ exists, assign $ q $ (if $ q $ appears somewhere) or the largest $ i $ such that $ \\text{first}_i \\leq j \\leq \\text{last}_i $, but this must be consistent with the non-overwrite constraint.  \n- Validate: For every $ i \\in \\{1, \\dots, q\\} $, the set $ \\{ j \\mid b_j = i \\} $ is an interval, and for every $ i < j $, if $ \\text{first}_j < \\text{first}_i < \\text{last}_j $, then $ \\text{last}_i \\leq \\text{last}_j $.  \n\n**Final Formal Statement**  \n\n**Definitions**  \nLet $ n, q \\in \\mathbb{Z}^+ $.  \nLet $ A = (a_1, \\dots, a_n) \\in \\{0, 1, \\dots, q\\}^n $.  \nLet $ B = (b_1, \\dots, b_n) \\in \\{1, \\dots, q\\}^n $ be a completion of $ A $, i.e., $ b_i = a_i $ if $ a_i \\neq 0 $, and $ b_i \\in \\{1, \\dots, q\\} $ otherwise.  \n\n**Constraints**  \n1. For each $ i \\in \\{1, \\dots, q\\} $, define $ I_i = \\{ j \\in \\{1, \\dots, n\\} \\mid b_j = i \\} $. Then $ I_i $ is a contiguous interval.  \n2. For all $ i < j $, if $ I_i \\cap I_j \\neq \\emptyset $, then $ I_i \\subseteq I_j $.  \n3. $ I_q \\neq \\emptyset $.  \n4. $ \\bigcup_{i=1}^q I_i = \\{1, \\dots, n\\} $.  \n\n**Objective**  \nDetermine whether there exists a completion $ B $ satisfying (1)–(4). If yes, output any such $ B $. Otherwise, output \"NO\".","simple_statement":null,"has_page_source":false}