На этот раз Пете на день рождения подарили скобочную последовательность. Петя оказался немного разочарован подарком, ведь он мечтал получить правильную скобочной последовательность, но ничего не сказал друзьям и решил сам немного доработать подарок.
Чтобы исправить последовательность Петя собирается не более одного раза взять произвольную скобку и вынуть её из последовательности (при этом оставшиеся скобки сдвигаются), после чего вставить её обратно в произвольное место в последовательности. Разворачивать скобку при этом не разрешается.
Напомним, что последовательность \(s\) из круглых скобок называется правильной, если:
- \(s\) является пустой;
- \(s\) равна «(\(t\))», где \(t\) — правильная скобочная последовательность;
- \(s\) равна \(t_1 t_2\), то есть конкатенации \(t_1\) и \(t_2\), где \(t_1\) и \(t_2\) являются правильными скобочными последовательностями.
Например, последовательности «(()())», «()» являются правильными, а «)(» и «())» нет. Помогите Пете понять, сможет ли он переставить скобку так, чтобы скобочная последовательность стала правильной.
Выходные данные
Выведите «Yes», если Петя сможет получить правильную скобочную последовательность сделав не более одной перестановки скобки. В противном случае выведите «No».
Примечание
В первом примере Петя может переставить первую скобку в конец, тогда получится строка «()», которая является правильной скобочной последовательностью.
Во втором примере не существует способа переставить одну скобку так, чтобы строка стала правильной скобочной последовательностью.
В третьем примере строка уже является правильной скобочной последовательностью, то есть ничего переставлять не надо.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
)(
|
Yes
|
|
2
|
3
(()
|
No
|
|
3
|
2
()
|
Yes
|
|
4
|
10
)))))(((((
|
No
|