您不小心落在沙漠中的相机拍摄了一张有趣的照片。该照片的分辨率为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
注意
前两个示例在语句中进行了描述。
在第三个示例中,所有像素都是白色,因此照片可以是斑马的照片。
在第四个示例中,第一个条纹的宽度等于三(白色),第二个条纹的宽度等于三(黑色),第三个条纹的宽度等于二(白色)。因此,并非所有条纹的长度都相等,因此这张照片不是斑马的照片。