Білл розробляє нову математичну теорію, яка описує людські емоції. Його останні дослідження присвячені вивченню того, наскільки хороші і погані дні впливають на спогади людей про різні періоди життя.

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

Тепер Білл хоче проаналізувати своє власне життя і знайти у ньому період максимальної значимості. Допоможіть йому це зробити.

Вхідні дані

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

Вихідні дані

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