Задача №575. Выражение
Петя - большой любитель математических головоломок. Недавно он прочитал в одном популярном журнале о новой головоломке. Он пытался ее решить несколько дней, но это ему так и не удалось. Помогите Пете справиться с неподдающейся задачей.
В ряд выписаны n чисел. Требуется поставить между каждой парой соседних чисел один из знаков "+" или "×" таким образом, чтобы значение получившегося выражения было как можно больше. Использовать скобки не разрешается.
Например, для последовательности чисел 1, 2, 3, 1, 2, 3 оптимально расставить знаки следующим образом: 1 + 2 × 3 × 1 × 2 × 3. Значение выражения в этом случае равно 37.
В первой строке вводится число \(n\) (2 <= \(n\) <= 200000). Вторая строка содержит \(n\) целых чисел - числа, между которыми следует расставить знаки. Все числа находятся в диапазоне от 0 до \(10^9\).
Выведите оптимальное выражение. В качестве знака "×" выводите символ "*" (звездочку). Если оптимальных решений несколько, выведите любое из них.
6 1 2 3 1 2 3
1+2*3*1*2*3