Волосатый бизнес

Условие
Одного неформала выгнали с работы, и теперь ему надо как-то зарабатывать себе на жизнь. Поразмыслив, он решил, что сможет иметь очень неплохие деньги на продаже собственных волос. Известно, что пункты приема покупают волосы произвольной длины стоимостью С за каждый сантиметр. Так как волосяной рынок является очень динамичным, то цена одного сантиметра волос меняется каждый день как и курс валют.

Неформал является очень хорошим бизнес-аналитиком. Он смог вычислить, какой будет цена одного сантиметра волос в каждый из ближайших N дней (для удобства пронумеруем дни в хронологическом порядке от 0 до N-1). Теперь он хочет определить, в какие из этих дней ему следует продавать волосы, чтобы по истечению всех N дней заработать максимальное количество денег.

Заметим, что волосы у неформала растут только ночью и вырастают на 1 сантиметр за ночь.

Следует также учесть, что до 0-го дня неформал с горя подстригся наголо и к 0-му дню длина его волос составляла 1 сантиметр.

Формат входных данных
В первой строке записано одно число N - количество дней.

Во второй строке записана последовательность чисел - стоимость сантиметра волос в каждый из дней.

Формат выходных данных
В качестве ответа нужно вывести максимальное количество денег, которое может заработать неформал.

входные данные выходные данные
5
73 31 96 24 46
380

0

0

Жадный алгоритм.

0