In my solution I had to solve following interesting subproblem.

Given an array. There is somewhere a unique cutpoint in this array. We don't know where, but we can check, if x is a cutpoint in O(1). We have to find this cutpoint, split array in two parts and do the same recursively on both parts. We need to do it faster than in O(n^2).

Solution:
For a segment (l, r) check for cutpoints in following order: l, r, l+1, r-1, l+2, r-2, ...

Thanks to author

Give me plz some tests. Please only good permutation :)

For this input:
3
1 2 3
Is this output correct:
(1,(2,3))

As an example of evaluating subexpression, (1, (2 * 3), 4) is shown. However, this is not a valid expression according to the grammar (* can only operate on sequences, not numbers). Which is correct?

What do you mean by "..." in formal definition? Is it the same as
<expression> ::= <sequence>{*<sequence>}
and
<sequence> ::= (<sequence element>{,<sequence element>}
or smth else?