← 返回题目列表

Codeforces · 952/C

C. 馄饨分类

中文机器翻译题面 查看原题

每个人都知道意大利面条。您决定自己实现模拟排序算法,但当您检查食品储藏室时,您发现意大利面条已经用完了!你唯一吃的意大利面是馄饨,但你不会让这阻止你......

你提出了以下算法。对于数组 ai 中的每个数字,构建一堆 ai 馄饨。该图显示了 ai = 4 时的堆栈。

按照相应数字在输入数组中出现的顺序将堆栈排列成一行。找到最高的一叠(如果有几叠最大高度,则使用最左边的一叠)。删除它并将其高度添加到输出数组的末尾。移动行中的堆栈,使它们之间没有间隙。重复该过程,直到所有堆栈都被移除。

起初,您对自己的算法非常满意,但是当您在更多输入上尝试它时,您意识到它并不总是产生正确的排序数组。事实证明,当两堆馄饨彼此相邻(在该过程的任何步骤)并且高度相差两个或更多时,较高堆叠的顶部馄饨会滑落到较低堆叠的顶部。

给定一个输入数组,找出所描述的算法是否能正确排序。

输入

输入的第一行包含一个数字 n (1 ≤ n ≤ 10) — 数组的大小。

输入的第二行包含 n 个空格分隔的整数 ai (1 ≤ ai ≤ 100) — 数组的元素。

输出

如果可以使用所描述的过程对数组进行排序,则输出“YES”,如果不能,则输出“NO”。

示例

输入 #1

3
1 2 3

输出 #1

YES

输入 #2

3
3 1 2

输出 #2

NO

注意

在第二个示例中,即使在第一次选择最高的堆栈之前,数组也会发生变化:高度为 3 的堆栈中的馄饨将在高度为 1 的堆栈上滑动,并且算法将输出数组 {2, 2, 2}。