Best run with its range

Problem

Extend the profit problem: print the largest total of a run of consecutive days, and the first and last day of that run (days are numbered from 1). If several runs give the same total, choose the one that starts first, and among those the one that ends first.

Input, output and limits

Input: Line 1: the integer n. Line 2: n integers separated by spaces.
Output: Three integers: the best sum, the first day and the last day.
Constraints: 1 ≤ n ≤ 10^5
-10^4 ≤ each integer ≤ 10^4

Examples

Example

Input

6
3 -5 4 -1 3 -2

Output

6 3 5

Days 3 to 5 give 6.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Remember the day on which the current run started.

Hint 2

Restart the run only when its sum is below zero, and replace the best only when current is strictly larger.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Reverse the wordsmedium
Common items of two sorted listshard
First non-repeating charactermedium
Longest palindromic substringhard
Valid anagrammedium

All Python problems

Problem

Input, output and limits

Examples

Hints

More Array & String Techniques problems

Problem

Input, output and limits

Examples

Hints

More Array & String Techniques problems