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