Камера, случайно оставленная вами в пустыне, сделала загадочный снимок. Снимок имеет разрешение в n пикселей по ширине, при этом в каждом столбце либо все пиксели черные, либо все белые. Таким образом, снимок можно представить в виде последовательности из n нулей и единиц, где 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 равно единице, то i-й столбец снимка состоит из белых пикселей.
Если на снимок могла попасть зебра, выведите «YES» (без кавычек). В противном случае выведите «NO».
Вы можете выводить каждую из букв в любом регистре (строчную или заглавную).
9
0 0 0 1 1 1 0 0 0
YES
7
0 0 0 1 1 1 1
NO
5
1 1 1 1 1
YES
8
1 1 1 0 0 0 1 1
NO
9
1 1 0 1 1 0 1 1 0
NO
Первые два примера разобраны в условии.
В третьем примере все столбцы пикселей белого цвета, поэтому зебра могла попасть на снимок.
В четвертом примере ширина первой полосы равна трем (она имеет белый цвет), ширина второй полосы равна трем (она имеет черный цвет), а ширина третьей полосы равна двум (она имеет белый цвет). Таким образом, не все полосы имеют одинаковую длину, поэтому зебра не могла попасть на снимок.
| VK Cup 2018 - Уайлд-кард Раунд 1 |
|---|
| Закончено |
