Последовательность \(a\) передается по сети следующим образом:
- последовательность \(a\) разбивают на отрезки (каждый элемент последовательности принадлежит ровно одному отрезку, каждый отрезок — это подряд идущие элементы последовательности);
- рядом с каждым отрезком, либо слева, либо справа от него, записывают длину этого отрезка;
- полученная последовательность \(b\) передаётся по сети.
Например, нужно было передать последовательность \(a = [1, 2, 3, 1, 2, 3]\). Допустим, что её разбили на отрезки следующим образом: \([\color{red}{1}] + [\color{blue}{2, 3, 1}] + [\color{green}{2, 3}]\). Тогда могли получиться следующие последовательности:
- \(b = [1, \color{red}{1}, 3, \color{blue}{2, 3, 1}, \color{green}{2, 3}, 2]\),
- \(b = [\color{red}{1}, 1, 3, \color{blue}{2, 3, 1}, 2, \color{green}{2, 3}]\),
- \(b = [\color{red}{1}, 1, \color{blue}{2, 3, 1}, 3, 2, \color{green}{2, 3}]\),
- \(b = [\color{red}{1}, 1,\color{blue}{2, 3, 1}, 3, \color{green}{2, 3}, 2]\).
Если бы было использовано другое разбиение на отрезки, то переданная последовательность могла бы быть другой.
Задана последовательность \(b\). Могла ли последовательность \(b\) быть передана по сети? Другими словами, существует ли такая последовательность \(a\), что при преобразовании \(a\) для передачи по сети могла получиться последовательность \(b\)?
Выходные данные
Для каждого набора входных данных в отдельной строке выведите:
- YES, если последовательность \(b\) могла быть передана по сети, то есть если последовательность \(b\) могла быть получена из некоторой последовательности \(a\) для передачи \(a\) по сети.
- NO в противном случае.
Вы можете выводить YES и NO в любом регистре (например, строки yEs, yes, Yes и YES будут распознаны как положительный ответ).
Примечание
В первом наборе входных данных последовательность \(b\) могла быть получена из последовательности \(a = [1, 2, 3, 1, 2, 3]\) со следующим разбиением: \([\color{red}{1}] + [\color{blue}{2, 3, 1}] + [\color{green}{2, 3}]\). Последовательность \(b\): \([\color{red}{1}, 1, \color{blue}{2, 3, 1}, 3, 2, \color{green}{2, 3}]\).
Во втором наборе входных данных последовательность \(b\) могла быть получена из последовательности \(a = [12, 7, 5]\) со следующим разбиением: \([\color{red}{12}] + [\color{green}{7, 5}]\). Последовательность \(b\): \([\color{red}{12}, 1, 2, \color{green}{7, 5}]\).
Во третьем наборе входных данных последовательность \(b\) могла быть получена из последовательности \(a = [7, 8, 9, 10, 3]\) со следующим разбиением: \([\color{red}{7, 8, 9, 10, 3}]\). Последовательность \(b\): \([5, \color{red}{7, 8, 9, 10, 3}]\).
В четвертом наборе входных данных не существует такой последовательности \(a\), что при изменении \(a\) для передачи по сети могла получиться последовательность \(b\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
9
1 1 2 3 1 3 2 2 3
5
12 1 2 7 5
6
5 7 8 9 10 3
4
4 8 6 2
2
3 1
10
4 6 2 1 9 4 9 3 4 2
1
1
|
YES
YES
YES
NO
YES
YES
NO
|