Problems
Предыдущая ПСП
Предыдущая ПСП
Дана правильная скобочная последовательность длины \textbf{N}.
Необходимо построить для данной последовательности предыдущую в лексикографическом порядке правильную скобочную последователельность.
\InputFile
В первой строке входного файла находится единственное натуральное число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10^5}, \textbf{N} -- четно). В следующей строке находится правильная скобочная последовательность из \textbf{N} круглых скобок.
\OutputFile
В выходной файл выведите строку из \textbf{N} символов - предыдущую в лексикографическом порядке правильную скобочную последовательность. Если предыдущей последовательности не существует, выведите "\textbf{No solution.}".
Input example #1
4 ()()
Output example #1
(())