Вам дана последовательность \([a_1,\ldots,a_n]\), где каждый элемент \(a_i\) равен либо \(0\), либо \(1\). Вы можете применить несколько (возможно, нулевое количество) операций к последовательности. В каждой операции вы выбираете два целых числа \(1\le l\le r\le |a|\) (где \(|a|\) — текущая длина \(a\)) и заменяете \([a_l,\ldots,a_r]\) одним элементом \(x\), где \(x\) — большинство \([a_l,\ldots,a_r]\).
Здесь большинство последовательности, состоящей из \(0\) и \(1\), определяется следующим образом: предположим, что в последовательности содержится \(c_0\) нулей и \(c_1\) единиц соответственно.
- Если \(c_0\ge c_1\), то большинство — \(0\).
- Если \(c_0<c_1\), то большинство — \(1\).
Например, предположим, что \(a=[1,0,0,0,1,1]\). Если мы выберем \(l=1,r=2\), то результирующая последовательность будет \([0,0,0,1,1]\). Если мы выберем \(l=4,r=6\), то результирующая последовательность будет \([1,0,0,1]\).
Определите, можно ли сделать \(a=[1]\) с помощью конечного количества операций.
Выходные данные
Для каждого набора входных данных, если возможно сделать \(a=[1]\), выведите YES. В противном случае выведите NO. Вы можете вывести ответ в любом регистре (верхний или нижний). Например, строки yEs, yes, Yes и YES будут распознаны как положительные ответы.
Примечание
В четвертом наборе входных данных изначально \(a=[1,0,0,0,0,0,0,0,1]\). Допустимая последовательность операций:
- Выберите \(l=2,r=8\) и примените операцию. \(a\) становится \([1,0,1]\).
- Выберите \(l=1,r=3\) и примените операцию. \(a\) становится \([1]\).