ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural SU contest. Petrozavodsk training camp. Summer 2008

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. Asterisk

Time limit: 0.5 second
Memory limit: 64 MB
Recently Cuckooland mathematicians have invented a new binary operation “asterisk”, which uses sequences as its arguments. Operation just appends the first sequence to the second. For example (2, 4) * (1, 3) = (1, 3, 2, 4). “Asterisk” operations in one expression are performed in order from the leftmost to the rightmost, but this order can be changed with brackets (operations in brackets are performed earlier). E. g. (3) * ((1, 5) * (2, 7)) = (2, 7, 1, 5, 3). Notice that if a sequence element is represented by an expression, then this expression is calculated first and then all nested brackets in this sequence are removed. For example, (1, ((2) * (3)), 4) = (1, (3, 2), 4) = (1, 3, 2, 4).
Now cuckoolanders want to use this operation for generating permutations. More precisely, they want to obtain a given permutation from permutation (1, 2, …, N) by adding brackets, commas and asterisks and evaluating the resulting expression.
The formal definition of expression follows.
<expression> ::= <sequence>[*<sequence>…]
<sequence> ::= (<sequence element>[,<sequence element>…])
<sequence element> ::= <number> | <expression>
<number> ::= 1|2|…|N


The first line contains an integer N (1 ≤ N ≤ 10000). The second line contains a permutation of numbers from 1 to N. These numbers are separated by spaces.


Output a single line — correct expression, the result of which is the given permutation. Numbers from 1 to N should appear in ascending order. The length of the expression should not exceed 100000 symbols. In case there is no such expression output “IMPOSSIBLE”. Note that expression must not contain spaces and all sequences must be enclosed in brackets.


3 4 2 1
5 1 2 6 4 3
Problem Author: Daniil Ayzenshteyn
Problem Source: Ural SU Contest. Petrozavodsk Summer Session, August 2008
To submit the solution for this problem go to the Problem set: 1670. Asterisk