← 返回题目列表

Codeforces · 926/C

C. 这是斑马吗?

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

您不小心落在沙漠中的相机拍摄了一张有趣的照片。该照片的分辨率为n像素宽度,并且该照片的每一列都是全白或全黑。因此,我们可以将照片表示为 n 个 0 和 1 的序列,其中 0 表示对应的列全是白色,1 表示对应的列是黑色。

您认为这张照片可以包含斑马。在这种情况下,整张照片应由几个(可能只有一个)宽度相等的交替黑白条纹组成。例如,照片[0, 0, 0, 1, 1, 1, 0, 0, 0]可以是斑马的照片,而照片[0, 0, 0, 1, 1, 1, 1]则不能,因为黑色条纹的宽度是3,而白色条纹的宽度是4。给定的照片是否可以是斑马的照片?

输入

第一行包含一个整数 n (1 ≤ n ≤ 100 000) — 照片的宽度。

第二行包含整数序列 a1, a2, ..., an (0 ≤ ai ≤ 1) — 照片的描述。如果 ai 为零,则第 i 列全黑。如果 ai 为 1,则第 i 列全是白色。

输出

如果照片可以是斑马照片,请打印“YES”(不带引号)。否则,打印“NO”。

您可以以任何大小写(大写或小写)打印每个字母。

示例

输入 #1

9
0 0 0 1 1 1 0 0 0

输出 #1

YES

输入 #2

7
0 0 0 1 1 1 1

输出 #2

NO

输入 #3

5
1 1 1 1 1

输出 #3

YES

输入#4

8
1 1 1 0 0 0 1 1

输出#4

NO

输入 #5

9
1 1 0 1 1 0 1 1 0

输出 #5

NO

注意

前两个示例在语句中进行了描述。

在第三个示例中,所有像素都是白色,因此照片可以是斑马的照片。

在第四个示例中,第一个条纹的宽度等于三(白色),第二个条纹的宽度等于三(黑色),第三个条纹的宽度等于二(白色)。因此,并非所有条纹的长度都相等,因此这张照片不是斑马的照片。