Задача №114975. Очередная скобочная последовательность

Вам дан массив \(a\), состоящий из \(n\) целых чисел \(a_1, a_2, \ldots, a_n\). Назовём стоимостью правильной скобочной последовательности \(s\) длины \(n\) сумму чисел в массиве \(a\), которые стоят на позициях, где в \(s\) стоят открывающие скобки « ( ».

Ваша задача состоит в том, чтобы найти правильную скобочную последовательность длины \(n\), стоимость которой максимальна.

В этой задаче правильная скобочная последовательность — это последовательность, которую можно построить по следующим правилам:

  • Пустая последовательность является правильной скобочной последовательностью;
  • Если \(A\) — правильная скобочная последовательность, то последовательность ( \(A\) ) является правильной скобочной последовательностью;
  • Если \(A\) и \(B\) – правильные скобочные последовательности, то последовательность \(AB\) (соединение этих последовательностей) является правильной скобочной последовательностью.

Например, последовательности (())() , () и (()(())) являются правильными, а )( , (() и (()))( не являются.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число \(t\) (\(1 \le t \le 10^5\)) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит единственное четное целое число \(n\) (\(2 \le n \le 2 \cdot 10^5\)) — длину массива \(a\).

Вторая строка каждого набора входных данных содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)) — элементы массива \(a\).

Гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(200\,000\).

Выходные данные

Для каждого набора входных данных выведите единственную строку \(s\) — правильную скобочную последовательность длины \(n\) с максимальной возможной стоимостью. Если правильных ответов несколько, выведите любой из них.

Примечание

В первом наборе входных данных существует единственная правильная скобочная последовательность длины \(2\) — « () ». Её стоимость равна \(1\), потому что \(a_1 = 1\).

Во втором наборе входных данных есть две правильные скобочные последовательности длины \(4\) — « (()) » и « ()() ». У первой стоимость равна \(a_1 + a_2 = 4 + 7 = 11\), у второй стоимость равна \(a_1 + a_3 = 4 + 1 = 5\), поэтому ответ равен « (()) ».

В четвёртом наборе входных данных ответом является « (())()(()) », стоимость которой равна \(a_1 + a_2 + a_5 + a_6 + a_7 = 1 + 2 + 1 + 2 + 2 = 8\).

Система оценки

Тесты к этой задаче состоят из 4 групп, не считая тесты из условия. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп.

Обозначим за \(N\) сумму \(n\) по всем тестовым набором внутри одного теста.

Доп. ограничения
Группа Баллы \(N\) \(a_i\) Необх. группы Комментарий
0 0 – – – Тесты из условия.
1 23 \(N \le 16\) – 0
2 17 \(N \le 1000\) – 0, 1
3 24 – \(a_i \le 2\) –
4 36 – – 0, 1, 2, 3
Примеры
Входные данные
5
2
1 10
4
4 7 1 1
4
1 1 5 3
10
1 2 1 1 1 2 2 2 1 1
6
3 3 1 3 4 4
Выходные данные
()
(())
()()
(())()(())
(())()
Сдать: для сдачи задач необходимо войти в систему