Хороші дні#4139
Білл розробляє нову математичну теорію, яка описує людські емоції. Його останні дослідження присвячені вивченню того, наскільки хороші і погані дні впливають на спогади людей про різні періоди життя.
Нещодавно Білл придумав методику, яка описує, наскільки хорошим чи поганим був день у людському житті, шляхом співставлення кожному дню деякого невід'ємного цілого числа. Білл називає це число емоційною значимістю цього дня. Чим більше це число, тим кращий цей день. Білл вважає, що значимість деякого періоду людського життя дорівнює сумі емоційних значимостей кожного з днів періоду, помноженій на мінімум емоційних значимостей днів цього періоду. Ця методика відображає те, що період, який у середньому може бути досить непоганим, може бути зіпсований одним поганим днем.
Тепер Білл хоче проаналізувати своє власне життя і знайти в ньому період максимальної значимості. Допоможіть йому це зробити.
Перший рядок містить кількість днів (1 \leq n \leq 100\,000) у житті Білла, які він хоче дослідити. Далі йдуть цілих чисел a_1,\, a_2,\, \ldots,\, a_n, усі в межах від до 10^6 — емоційні значимості днів. Вхідні числа відокремлюються пробілами та переведеннями рядка.
У першому рядку виведіть максимальну значимість періоду життя Білла. У другому рядку виведіть два числа та (l \leq r), які означають, що значимість періоду з -го по -ий день (включно) у житті Білла була максимально можливою.
Приклад 1