eolymp
bolt
Try our new interface for solving problems
Məsələlər

Звёздочка

Звёздочка

Недавно математики Кукуляндии придумали новую бинарную операцию "звёздочка", аргументами которой являются последовательности. Операция просто приписывает первую последовательность в конец второй. Например,\textbf{(2, 4) * (1, 3) = (1, 3, 2, 4)}. Порядок выполнения нескольких операций "звёздочка" в одной строке --- слева направо, но, используя скобки, порядок можно изменить (операции в скобках выполняются раньше). Так, \textbf{(3) * ((1, 5) * (2, 7)) = (2, 7, 1, 5, 3)}. Заметим, что если в качестве одного из элементов последовательности указано выражение, то сперва вычисляется его значение, а потом в получившейся последовательности стираются внутренние скобки. Например, \textbf{(1, ((2) * (3)), 4) = (1, 3, 2, 4)}. Теперь кукуляндцы хотят использовать эту операцию для генерации перестановок. Точнее, они хотят получить заданную перестановку из перестановки \textbf{(1, 2, …, N)}, дописав скобки, запятые и звёздочки и вычислив значение получившегося выражения. Приведём формальное определение \textbf{выражения}. \textbf{<выражение> ::= <последовательность>\[*<последовательность>…\]} \textbf{<последовательность> ::= (<элемент>\[,<элемент>…\])} \textbf{<элемент> ::= <число> | <выражение>} \textbf{<число> ::= 1|2|…|N} \InputFile В первой строке записано число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10000}). Во второй строке записана перестановка чисел от \textbf{1} до \textbf{N}. Числа в строке разделены пробелом. \OutputFile Выведите единственную строку --- корректное выражение, в результате вычисления значения которого получится данная перестановка. При этом в выражении числа от \textbf{1} до \textbf{N} должны идти в возрастающем порядке. Длина выражения не должна превосходить \textbf{100000} символов. Если искомого выражения не существует, выведите "\textbf{IMPOSSIBLE}". Обратите внимание на то, что в выражении не должно быть пробелов и все последовательности обязательно должны быть заключены в скобки.
Zaman məhdudiyyəti 0.5 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
4
3 4 2 1
Çıxış verilənləri #1
(((1)*(2))*((3),(4)))
Müəllif Даниил Айзенштейн
Mənbə Ural SU Contest. Petrozavodsk Summer Session, August 2008