В масиві з \(N\) чисел знайти непустий підмасив з максимальною сумою.

Формат вхідних даних

В першому рядку ціле число \(N\), кількість елементів (\(1 \le N \le 10^6\)).
В наступному рядку \(N\) цілих чисел \(Ai\) - елементи масиву (\(-10000 \le Ai \le 10000\)).

Формат вихідних даних

В першому рядку виведіть максимальну суму непустого підмасиву.
В другому рядку виведіть індекси початку і кінця цього підмасиву.
Якщо таких підмасивів декілька, виведіть той який починається раніше.
Якщо кілька таких підмасивів починаються в однаковому індексі, виведіть той з них, який закінчується раніше.

Приклад вхідних даних

10
2 -7 5 5 -3 5 -1 8 -100 2

Приклад вихідних даних

19
3 8