Задачі
Попередня ПДП
Попередня ПДП
Задано правильну дужкову послідовність довжини N.
Необхідно побудувати для заданої послідовності попередню у лексикографічному порядку правильну дужкову послідовність.
Вхідні дані
У першому рядку вхідного файлу знаходиться єдине натуральне число N (1 ≤ N ≤ 10^5, N – парне). У наступному рядку знаходиться правильна дужкова послідовнвсть з N круглих дужок.
Вихідні дані
У вихідний файл виведіть рядок з N символів - попередню у лексикографічному порядку правильну дужкову послідовність. Якщо попередньої послідовності не існує, виведіть "No solution".
Приклад
Вхідні дані #1
4 ()()
Вихідні дані #1
(())