Магическая ПСП

면접 대비

시간 제한2초메모리 제한1024 MB

요약

괄호 쌍 사이의 거리들이 주어질 때, 각 쌍의 거리가 정확히 그 값이 되는 길이 2n의 올바른 괄호 문자열을 하나 찾는다.

난이도: 보통10점 중 5점
유형: 백트래킹, 구현, 완전 탐색
정답자: 아직 제출이 없습니다

문제

Иэн и Барли нашли древнюю книгу с заклинаниями, и Иэн решил испробовать одно из них.

К сожалению, в книге написано не само заклинание, а только его описание. Известно, что заклинание является правильной скобочной последовательностью (ПСП). ПСП это строка, состоящая из символов <<(>> и <<)>>. Пустая строка является ПСП. Конкатенация двух, возможно разных, ПСП является ПСП. ПСП, взятая в скобки, является ПСП. Две скобки в ПСП называются парными, если подстрока, начинающаяся сразу после первой из скобок и заканчивающаяся прямо перед второй, является ПСП. Несложно доказать, что в любой ПСП длины $n \cdot 2$ есть ровно $n$ пар парных скобок. Для простоты, будем называть их просто парами скобок.

Известно, что заклинание содержит $n$ пар скобок. А также, известно мультимножество расстояний между скобками в каждой паре. Иными словами, для каждой пары скобок было найдено $a\_i$ --- количество символов между ними.

Теперь Иэн пытается восстановить заклинание. Помогите ему найти любую подходящую ПСП, либо сообщите, что такой не существует.

입력

В первой строке дано одно целое число $n$ --- количество пар скобок в заклинании ( $1 \le n \le 20$ ). Во второй строке даны $n$ целых чисел $a\_i$ --- мультимножество расстояний между скобками в каждой паре ( $0 \le a\_i \le n \cdot 2$ ).

출력

Если существует ПСП, которая удовлетворяет всем ограничениям, в первой строке выведите <<Yes>>, а во второй --- строку из символов <<(>> и <<)>> длины $n \cdot 2$ --- подходящую ПСП. Если существует несколько решений, выведите любое.

Если подходящей ПСП не существует, в единственной строке выведите <<No>>.

예제5

예제 1
입력
```
1
0
```
예상 출력
```
Yes
()
```
예제 2
입력
```
2
0 0
```
예상 출력
```
Yes
()()
```
예제 3
입력
```
2
2 0
```
예상 출력
```
Yes
(())
```
예제 4
입력
```
1
2
```
예상 출력
```
No
```
예제 5
입력
```
5
0 0 0 2 6
```
예상 출력
```
Yes
()(()(()))
```