Как известно, любая задача, в которой не требуется использовать сложные структуры данных, считается конструктивной. Вам предлагается решить одну из таких задач.
Дан массив \(a\) из \(n\) целых неотрицательных чисел. Вам разрешается ровно один раз выполнить следующую операцию: выбрать какой-то непустой подотрезок \(a_l, a_{l+1}, \ldots, a_r\) массива \(a\) и целое неотрицательное число \(k\), и присвоить значение \(k\) всем элементам массива на выбранном подотрезке.
Требуется выяснить, можно ли увеличить \(\operatorname{MEX}(a)\) ровно на единицу, проделав такую операцию. Другими словами, если до выполнения операции выполнялось \(\operatorname{MEX}(a) = m\), то после операции должно быть верно, что \(\operatorname{MEX}(a) = m + 1\).
Напомним, что \(\operatorname{MEX}\) набора чисел \(c_1, c_2, \ldots, c_k\) определяется как наименьшее неотрицательное целое число \(x\), которое не встречается в наборе чисел \(c\).
Выходные данные
Для каждого набора входных данных выведите «Yes», если можно увеличить \(\operatorname{MEX}(a)\) ровно на единицу, выполнив операцию из условия ровно один раз, иначе выведите «No».
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Примечание
В первом наборе входных данных \(\operatorname{MEX}(a) = 0\). Если присвоить всем элементам \(a\) значение \(0\), то \(\operatorname{MEX}\) полученного массива будет равен \(1\), и тем самым увеличится на единицу.
Во втором наборе входных данных \(\operatorname{MEX}(a) = 1\). Если присвоить значение \(1\) элементам \(a\) на отрезке от \(2\) до \(3\), то получится массив \([0, 1, 1, 0]\), для которого \(\operatorname{MEX}\) равен \(2\), и тем самым увеличился на единицу по сравнению с изначальным.
Можно показать, что в третьем и четвертом наборах входных данных невозможно выполнить операцию, чтобы значение \(\operatorname{MEX}(a)\) увеличилось ровно на единицу.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
1 2 1
4
0 2 2 0
4
3 2 0 2
1
0
|
Yes
Yes
No
No
|