| Автор: | Восьмая всероссийская командная олимпиада школьников по программированию | Ограничение времени: | 2 сек | |
| Входной файл: | expr.in | Ограничение памяти: | 256 Мб | |
| Выходной файл: | expr.out |
Петя — большой любитель математических головоломок. Недавно он прочитал в одном популярном журнале о новой головоломке. Он пытался ее решить несколько дней, но это ему так и не удалось. Помогите Пете справиться с неподдающейся задачей.
В ряд выписаны n чисел. Требуется поставить между каждой парой соседних чисел один из знаков "+" или × таким образом, чтобы значение получившегося выражения было как можно больше. Использовать скобки не разрешается.
Например, для последовательности чисел 1, 2, 3, 1, 2, 3 оптимально расставить знаки следующим образом: 1 + 2 × 3 × 1 × 2 × 3. Значение выражения в этом случае равно 37.
Первая строка входного файла содержит число n. Вторая строка содержит n целых чисел — числа, между которыми следует расставить знаки.
Выведите в выходной файл оптимальное выражение. В качестве знака × выводите символ "*" (звездочку). Если оптимальных решений несколько, выведите любое из них.
2 ≤ n ≤ 200 000
Все числа находятся в диапазоне от 0 до 109.
| № | Входной файл (expr.in) |
Выходной файл (expr.out) |
|---|---|---|
| 1 |
|
|