Кошек привлекает «кис-кис-кис», но Эвирир, будучи достойным англоговорящим драконом, отзывается только на «pspspsp» с особыми условиями...
Дана строка \(s = s_1s_2\ldots s_n\) длины \(n\), состоящая из символов p, s и . (точка). Определите, существует ли перестановка\(^{\text{∗}}\) \(p\) длины \(n\), такая, что для каждого целого \(i\) (\(1 \le i \le n\)):
- Если \(s_i\) равно p, то \([p_1, p_2, \ldots, p_i]\) образует перестановку (длины \(i\));
- Если \(s_i\) равно s, то \([p_i, p_{i+1}, \ldots, p_{n}]\) образует перестановку (длины \(n-i+1\));
- Если \(s_i\) равно ., то дополнительных ограничений нет.
Выходные данные
Для каждого набора входных данных в первой строке выведите YES или NO. Выведите YES, если искомая перестановка существует, и NO в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Примечание
Для первого набора входных данных одна подходящая перестановка такова: \(p = [3, 4, 1, 2]\). Для неё выполняются все условия:
- \(s_1 =\) s : \([p_1, p_2, p_3, p_4] = [3, 4, 1, 2]\) образует перестановку.
- \(s_2 =\) . : Никаких дополнительных ограничений.
- \(s_3 =\) s : \([p_3, p_4] = [1, 2]\) образует перестановку.
- \(s_4 =\) p : \([p_1, p_2, p_3, p_4] = [3, 4, 1, 2]\) образует перестановку.
Для второго набора входных данных можно доказать, что не существует перестановки, удовлетворяющей всем ограничениям.
Для третьего набора входных данных одной перестановкой, удовлетворяющей условиям, является \(p = [1, 2, 3, 4, 5]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
4
s.sp
6
pss..s
5
ppppp
2
sp
4
.sp.
8
psss....
1
.
8
pspspsps
20
....................
|
YES
NO
YES
YES
NO
NO
YES
NO
YES
|