Previous PDP#5150
A valid bracket sequence of length is provided.
Your task is to find the previous valid bracket sequence in lexicographical order for the given sequence.
The first line of the input contains a single natural number (1 \leq N \leq 10^5, and is even). The second line contains a valid bracket sequence consisting of round brackets.
Output a string of characters representing the previous valid bracket sequence in lexicographical order. If there is no such sequence, output "No solution".
Example 1