{"raw_statement":[{"iden":"statement","content":"Everybody knows of [spaghetti sort](https://en.wikipedia.org/wiki/Spaghetti_sort). You decided to implement an analog sorting algorithm yourself, but as you survey your pantry you realize you're out of spaghetti! The only type of pasta you have is ravioli, but you are not going to let this stop you...\n\nYou come up with the following algorithm. For each number in the array _a__i_, build a stack of _a__i_ ravioli. The image shows the stack for _a__i_ = 4.\n\n<center>![image](https://espresso.codeforces.com/e1f99e79e45a83cec6e4d9df0a128a64f53473c0.png)</center>Arrange the stacks in one row in the order in which the corresponding numbers appear in the input array. Find the tallest one (if there are several stacks of maximal height, use the leftmost one). Remove it and add its height to the end of the output array. Shift the stacks in the row so that there is no gap between them. Repeat the procedure until all stacks have been removed.\n\nAt first you are very happy with your algorithm, but as you try it on more inputs you realize that it doesn't always produce the right sorted array. Turns out when two stacks of ravioli are next to each other (at any step of the process) and differ in height by two or more, the top ravioli of the taller stack slides down on top of the lower stack.\n\nGiven an input array, figure out whether the described algorithm will sort it correctly."},{"iden":"input","content":"The first line of input contains a single number _n_ (1 ≤ _n_ ≤ 10) — the size of the array.\n\nThe second line of input contains _n_ space-separated integers _a__i_ (1 ≤ _a__i_ ≤ 100) — the elements of the array."},{"iden":"output","content":"Output \"YES\" if the array can be sorted using the described procedure and \"NO\" if it can not."},{"iden":"examples","content":"Input\n\n3\n1 2 3\n\nOutput\n\nYES\n\nInput\n\n3\n3 1 2\n\nOutput\n\nNO"},{"iden":"note","content":"In the second example the array will change even before the tallest stack is chosen for the first time: ravioli from stack of height 3 will slide on the stack of height 1, and the algorithm will output an array {2, 2, 2}."}],"translated_statement":[{"iden":"statement","content":"每个人都听说过意大利面排序。你决定自己实现一个类似的模拟排序算法，但当你检查厨房储物柜时，发现你没有意大利面了！你唯一有的面食是意大利馄饨，但你不会因此放弃...\n\n你提出了以下算法：对于数组中的每个数字 #cf_span[ai]，堆叠 #cf_span[ai] 个意大利馄饨。图示展示了 #cf_span[ai = 4] 的堆叠。\n\n将这些堆叠按输入数组中对应数字的顺序排成一行。找到最高的那个（如果有多个相同最大高度的堆叠，选择最左边的）。将它移除，并将其高度添加到输出数组的末尾。然后将剩余的堆叠向左移动，使它们之间没有空隙。重复此过程，直到所有堆叠都被移除。\n\n起初你对这个算法非常满意，但当你用更多输入测试时，发现它并不总是能产生正确的排序结果。事实上，当两个意大利馄饨堆叠相邻（在任何步骤中）且高度差为 2 或以上时，较高的堆叠顶部的馄饨会滑落到较低的堆叠上。\n\n给定一个输入数组，判断上述算法是否能正确地对其进行排序。\n\n输入的第一行包含一个单独的数字 #cf_span[n] (#cf_span[1 ≤ n ≤ 10]) —— 数组的大小。\n\n第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[ai] (#cf_span[1 ≤ ai ≤ 100]) —— 数组的元素。\n\n如果数组可以通过上述过程排序，则输出 \"YES\"，否则输出 \"NO\"。\n\n在第二个例子中，甚至在第一次选择最高堆叠之前，数组就已经发生变化了：高度为 3 的堆叠中的馄饨会滑落到高度为 1 的堆叠上，算法最终输出数组 #cf_span[{2, 2, 2}]。"},{"iden":"input","content":"The first line of input contains a single number #cf_span[n] (#cf_span[1 ≤ n ≤ 10]) — the size of the array.The second line of input contains #cf_span[n] space-separated integers #cf_span[ai] (#cf_span[1 ≤ ai ≤ 100]) — the elements of the array."},{"iden":"output","content":"Output \"YES\" if the array can be sorted using the described procedure and \"NO\" if it can not."},{"iden":"examples","content":"输入31 2 3输出YES输入33 1 2输出NO"},{"iden":"note","content":"在第二个例子中，甚至在第一次选择最高堆叠之前，数组就已经发生变化了：高度为 3 的堆叠中的馄饨会滑落到高度为 1 的堆叠上，算法最终输出数组 #cf_span[{2, 2, 2}]。"}],"sample_group":[],"show_order":[],"formal_statement":"Given an array $ A = [a_1, a_2, \\dots, a_n] $ of positive integers, simulate the following process:\n\n1. Construct $ n $ vertical stacks, where stack $ i $ has height $ a_i $.\n2. While stacks remain:\n   - If any two adjacent stacks differ in height by 2 or more, then ravioli slide from the taller stack to the shorter one until all adjacent pairs differ by at most 1. Specifically, for each adjacent pair $ (h_i, h_{i+1}) $, if $ |h_i - h_{i+1}| \\geq 2 $, then transfer one ravioli from the taller to the shorter until all adjacent differences are ≤1. This sliding occurs **before** any stack is removed and may propagate.\n   - Then, select the leftmost tallest stack, remove it, and append its height to the output array.\n   - Shift remaining stacks left to close the gap.\n3. The algorithm \"succeeds\" if the output array is non-decreasing.\n\nDetermine whether the output array produced by this process is sorted in non-decreasing order.\n\n---\n\n**Formal Problem Statement:**\n\nLet $ A = [a_1, a_2, \\dots, a_n] \\in \\mathbb{Z}_{>0}^n $.\n\nDefine a function $ f: \\mathbb{Z}_{>0}^k \\to \\mathbb{Z}_{>0}^k $ that stabilizes a stack configuration under the sliding rule:\n\n> For a sequence $ S = [s_1, s_2, \\dots, s_k] $, repeatedly apply:  \n> For each $ i = 1 $ to $ k-1 $:  \n> If $ s_i \\geq s_{i+1} + 2 $, then set $ s_i \\gets s_i - 1 $, $ s_{i+1} \\gets s_{i+1} + 1 $.  \n> If $ s_{i+1} \\geq s_i + 2 $, then set $ s_{i+1} \\gets s_{i+1} - 1 $, $ s_i \\gets s_i + 1 $.  \n> Continue until no such adjacent pair exists.  \n> Denote the resulting stable configuration as $ f(S) $.\n\nDefine the sorting process $ \\text{RavioliSort}(A) $:\n\n- Initialize $ S = A $.\n- Initialize output $ O = [] $.\n- While $ S \\neq \\emptyset $:\n  1. $ S \\gets f(S) $\n  2. Let $ m = \\max(S) $, and let $ i $ be the smallest index such that $ s_i = m $.\n  3. Append $ m $ to $ O $.\n  4. Remove $ s_i $ from $ S $, and shift elements left to form a contiguous array.\n- Return $ O $.\n\n**Question:** Is $ O $ non-decreasing?\n\nOutput \"YES\" if $ O $ is non-decreasing; \"NO\" otherwise.","simple_statement":null,"has_page_source":false}