Задача №3569. Хорошие дни
Билл разрабатывает новую математическую теорию, описывающую человеческие эмоции. Его последние исследования посвящены изучению того, насколько хорошие и плохие дни влияют на воспоминания людей о различных периодах жизни.
Недавно Билл придумал методику, которая описывает, насколько хорошим или плохим был день человеческой жизни с помощью сопоставления дню некоторого неотрицательного целого числа. Билл называет это число эмоциональной значимостью этого дня. Чем больше это число, тем лучше этот день. Билл полагает, что значимость некоторого периода человеческой жизни равна сумме эмоциональных значимостей каждого из дней периода, помноженной на минимум эмоциональных значимостей дней этого периода. Эта методика отражает то, что период, который в среднем может быть весьма неплох, бывает испорчен одним плохим днем.
Теперь Билл хочет проанализировать свою собственную жизнь и найти в ней период максимальной значимости. Помогите ему это сделать.
Первая строка входного файла содержит число \(n\) — количество дней в жизни Билла, которые он хочет исследовать (\(1 \le n \le 100\,000\)). Оставшаяся часть файла содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\), все в пределах от 0 до \(10^6\) — эмоциональные значимости дней. Числа во входном файле разделяются пробелами и переводами строки.
В первой строке выходного файла выведите максимальную значимость периода жизни Билла. Во второй строке выведите два числа \(l\) и \(r\), означающие, что значимость периода с \(l\)-го по \(r\)-й день (включительно) в жизни Билла была максимально возможной.
6 3 1 6 4 5 2
60 3 5