405835: GYM102133 F Financial Reports

Financial analysts of "WeRRich" company are working on a current annual report. They have n data points of company's shares fluctuations sorted by time stamps in chronological order. The analysts are required to compute the most wealthy period, i.e. a consecutive non-empty time interval, which has maximum sum of fluctuations within a year period.

Unfortunately, top management of the company is not satisfied with the annual report results, hence analysts have decided to adjust the report by swapping two fluctuations in the time series. It looks like a perfect crime, but financiers are not able to develop efficient enough algorithm to perform the plan. Now they have to ask software engineers to help them out. So they are required to determine the fluctuation indices to swap and a maximum fluctuation sum, which is possible to obtain as a result.

First line contains positive integer n – a number of fluctuations of shares within a financial year.

Second line contains exactly n integers a_i – values of fluctuations given in chronological order.

The maximal fluctuations sum during the most wealthy period should be printed in a first line.

Second line should contain two different numbers – indices of swapped fluctuations. If multiple solution exist, you may output any of them.

5
1 -2 -3 4 -5

5
4 2