В дощечку в ряд вбито 10 гвоздиков, таким образом, получилось 9 последовательных промежутков между ними. Длины промежутков (подряд, слева направо) оказались равны

7, 2, 8, 4, 3, 9, 5, 1, 6.

Между некоторыми соседними гвоздиками можно натянуть верёвочку, будем считать длину этой верёвочки равной длине промежутка. Вам необходимо привязать верёвочки так, чтобы к каждому гвоздику была привязана верёвочка хотя бы с одной стороны, при этом суммарная длина всех верёвочек была бы минимальной.

Ответ запишите в виде последовательности из 9 чисел, равных 0 или 1. Число 0 означает, что в соответствующем промежутке нет верёвочки, число 1 означает, что в этом промежутке есть верёвочка.

Условие, что к каждому гвоздику привязана хотя бы одна верёвочка, означает, что в ответе нет двух нулей подряд, а также, что первым и последним символом ответа является 1.
Например, пусть в задании было дано 5 гвоздиков и 4 промежутка длиной 1, 2, 3, 4. Длина верёвочек будет минимальной, если привязать верёвочки в промежутках 1, 2 и 4. Ответ тогда следовало бы записать в виде 1101.


А какая будет длина всех проведённых при этом линий? Например, при n = 3 длина всех линий равна 18.

Ответом на эту задачу является некоторое выражение, которое может содержать целые числа, переменную n, операции сложения (обозначаются «+»), вычитания (обозначаются «−»), умножения (обозначаются «*»), деления (обозначаются «/») и круглые скобки для изменения порядка действий. Запись вида «2n» для обозначения произведения числа 2 и переменной n неверная, нужно писать «2 * n». Выражение вида n2 нужно записывать с использованием операции умножения: «n * n».

Ваше выражение должно давать правильный ответ для любых n, например, для n = 3 значение выражения должно быть равно 18.

Пример правильной формы записи ответа.

(n + 1) * (n - 2) / 2