У вас есть массив \(a\) размера \(n\), состоящий только из нулей и единиц, и целое число \(k\). За одну операцию вы можете выполнить одно из двух следующих действий:
- Выберите \(2\) последовательных элемента \(a\) и замените их на их минимум (то есть сделайте \(a := [a_{1}, a_{2}, \ldots, a_{i-1}, \min(a_{i}, a_{i+1}), a_{i+2}, \ldots, a_{n}]\) для некоторого \(1 \le i \le n-1\)). Эта операция уменьшает размер \(a\) на \(1\).
- Выберите \(k\) последовательных элементов \(a\) и замените их на их максимум (то есть сделайте \(a := [a_{1}, a_{2}, \ldots, a_{i-1}, \max(a_{i}, a_{i+1}, \ldots, a_{i+k-1}), a_{i+k}, \ldots, a_{n}]\) для некоторого \(1 \le i \le n-k+1\)). Эта операция уменьшает размер \(a\) на \(k-1\).
Определите, возможно ли превратить \(a\) в \([1]\) после нескольких (возможно, нуля) операций.
Выходные данные
Для каждого набора входных данных, если возможно превратить \(a\) в \([1]\), выведите «YES», иначе выведите «NO».
Примечание
В первом наборе входных данных вы можете выполнить операцию второго типа над вторым и третьим элементами так, что \(a\) будет равно \([0, 1]\), затем вы можете выполнить операцию второго типа над первым и вторым элементами, после чего \(a\) превратится в \([1]\).
Очевидно, что в четвертом наборе входных данных вы не можете получить ни одного значения \(1\), что бы вы ни делали.
В пятом наборе входных данных вы можете сначала выполнить операцию второго типа над первыми тремя элементами, чтобы \(a\) стало равно \([1, 0, 0, 1]\), затем выполнить операцию второго типа над элементами со второй позиции по четвертую так, что \(a\) станет равно \([1, 1]\), и, наконец, выполнить операцию первого типа над оставшимися элементами так, что \(a\) превратится в \([1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
3 2
0 1 0
5 3
1 0 1 1 0
2 2
1 1
4 4
0 0 0 0
6 3
0 0 1 0 0 1
7 5
1 1 1 1 1 1 1
5 3
0 0 1 0 0
|
YES
YES
YES
NO
YES
YES
YES
|