← 返回题目列表

Codeforces · 1197/B

B. 支柱

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

有 $$$n$$$ 柱子排成一排,编号从 $$$1$$$ 到 $$$n$$$。

最初,每个柱只包含一个磁盘。第$$$i$$$柱包含半径为$$$a_i$$$的圆盘。

您可以将这些圆盘从一根柱子移动到另一根柱子。如果满足所有这些条件,您可以从柱子 $$$i$$$ 上取出一个圆盘并将其放在柱子 $$$j$$$ 顶部:

1. 支柱$$$i$$$ 和$$$j$$$ 之间没有其他支柱。正式来说,这意味着 $$$|i - j| = 1$$$;
2. 支柱$$$i$$$ 恰好包含一个磁盘;
3. 支柱 $$$j$$$ 不包含磁盘,或者支柱 $$$j$$$ 上最上面的磁盘的半径严格大于您移动的磁盘的半径。

当您将一个磁盘放置在已经有一些磁盘的柱子上时,您会将新磁盘放置在先前放置的磁盘之上,因此如果您尝试将另一个磁盘放置在同一柱子上,则新磁盘将用于检查第三个条件。

你可以多次取出任何圆盘并将其放置在其他柱子上,前提是每次执行此操作时都满足上述所有三个条件。现在你想知道,是否可以将所有 $$$n$$$ 磁盘同时放置在同一根柱子上?

输入

第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — 柱子的数量。

第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_i$$$ ($$$1 \le a_i \le n$$$),其中 $$$a_i$$$ 是最初放置在第 $$$i$$$ 柱上的圆盘的半径。所有数字 $$$a_i$$$ 都是不同的。

输出

如果可以将所有圆盘同时放置在同一个柱子上,则打印“是”,否则打印“否”。您可以在任何情况下打印每个字母(YES、yes、Yes 都将被识别为肯定答案,NO、no 和 nO 都将被识别为否定答案)。

示例

输入 #1

4
1 3 4 2

输出 #1

YES

输入 #2

3
3 1 2

输出 #2

NO

注意

在第一种情况下,可以使用以下操作序列将所有磁盘放置在支柱 $$$3$$$ 上:

1. 从柱子$$$2$$$上取出半径为$$$3$$$的圆盘,并将其放置在柱子$$$3$$$的顶部;
2. 从柱子$$$1$$$上取出半径为$$$1$$$的圆盘,并将其放置在柱子$$$2$$$的顶部;
3. 从柱子$$$4$$$上取出半径为$$$2$$$的圆盘,并将其放在柱子$$$3$$$的顶部;
4. 从支柱 $$$2$$$ 上取出半径为 $$$1$$$ 的圆盘,并将其放置在支柱 $$$3$$$ 的顶部。