You were the Chosen One! You were supposed to destroy the Sith, not join them. You were supposed to bring balance to the Force, not leave it in darkness.
The Force, represented by the characters
) is now unbalanced! The Force is balanced if it is one of the following:
AB, where ~A~ and ~B~ are balanced
(A), where ~A~ is balanced
Kenobi can invert (i.e. turn a
( character to
), or vice versa) at most 1 character in the Force. Given the sequence which represents the Force, print
YES if Kenobi can balance it, and
The input will contain a single string, ~S~, the sequence which represents the Force.
YES if it can be balanced, and
For all subtasks, ~S~ will have an even number of characters.
Subtask 1 [20%]
~2 \le |S| \le 1\,000~
Subtask 2 [80%]
~2 \le |S| \le 10^5~