Билл разрабатывает новую математическую теорию, описывающую человеческие эмоции. Его последние исследования посвящены изучению того, насколько хорошие и плохие дни влияют на воспоминания людей о различных периодах жизни.

Недавно Билл придумал методику, которая описывает, насколько хорошим или плохим был день человеческой жизни с помощью сопоставления дню некоторого неотрицательного целого числа. Билл называет это число эмоциональной значимостью этого дня. Чем больше это число, тем лучше этот день. Билл полагает, что значимость некоторого периода человеческой жизни равна сумме эмоциональных значимостей каждого из дней периода, умноженной на минимум эмоциальных значимостей дней этого периода. Эта методика отражает то, что период, который в среднем может быть весьма неплох, бывает испорчен одним плохим днём.

Теперь Билл хочет проанализировать свою собственную жизнь и найти в ней период максимальной значимости. Помогите ему это сделать.

Входные данные

Первая строка содержит количество дней n (1 ≤ n ≤ 100000) в жизни Билла, которые он хочет исследовать. Оставшаяся часть входных данных содержит n целых чисел a1, a2, ..., an, все в пределах от 0 до 106 - эмоциональные значимости дней. Входные числа разделяются пробелами и переводами строки.

Выходные данные

В первой строке выведите максимальную значимость периода жизни Билла. Во второй строке выведите два числа l и r (l ≤ r), означающие, что значимость периода с l-го по r-ый день (включительно) в жизни Билла была максимально возможной.