21463번 - Выражение 스페셜 저지다국어

Петя --- большой любитель математических головоломок. Недавно он прочитал в одном популярном журнале о новой головоломке. Он пытался ее решить несколько дней, но это ему так и не удалось. Помогите Пете справиться с неподдающейся задачей.

В ряд выписаны $n$ чисел. Требуется поставить между каждой парой соседних чисел один из знаков <<+>> или <<$\times$>> таким образом, чтобы значение получившегося выражения было как можно больше. Использовать скобки не разрешается.

Например, для последовательности чисел $1, 2, 3, 1, 2, 3$ оптимально расставить знаки следующим образом: $1 + 2 \times 3 \times 1 \times 2 \times 3$. Значение выражения в этом случае равно $37$.

Первая строка входного файла содержит число $n$ ($2 \le n \le 200\,000$). Вторая строка содержит $n$ целых чисел --- числа, между которыми следует расставить знаки. Все числа находятся в диапазоне от 0 до $10^9$.

Выведите в выходной файл оптимальное выражение. В качестве знака <<$\times$>> выводите символ <<*>> (звездочку). Если оптимальных решений несколько, выведите любое из них.