The government of Siruseri has just commissioned one of the longest and most modern railway routes in the world. This route runs the entire length of Siruseri and passes through many of the big cities and a large number of small towns and villages in Siruseri.
The railway stations along this route have all been constructed keeping in mind the comfort of the travellers. Every station has big parking lots, comfortable waiting rooms and plenty of space for eateries. The railway authorities would like to contract out the catering services of these eateries.
The Siruseri Economic Survey has done a through feasibility study of the different stations and documented the expected profits (or losses) for the eateries in all the railway stations on this route. The authorities would like to ensure that every station is catered to. To prevent caterers from bidding only for profitable stations, the authorities have decided to give out catering contracts for contiguous segments of stations.
The minister in charge realises that one of the bidders is his bitter adversary and he has decided to hand out as useless a segment as possible to him. On the other hand, he does not want to be seen to be blatantly unfair by handing out a large loss-making section to the adversary. Instead he wants to find the largest segment whose sum is closest to $0$, so that his adversary spends all his time running a large number of canteens and makes either a small loss or a small profit or, even better, nothing at all!
In other words, if the profits/losses at the stations are $p_1, p_2, ..., p_N$ the minister would like to handover a sequence $i, i+1, ..., j$ such that the absolute value of $p_i + p_{i+1} + ... + p_j$ is minimized. If there is more than one sequence with this minimum absolute value then he would like to hand over the longest one.
For example, suppose there are $8$ stations along the line and their profitability is as follows:
$ $
Station              1    2    3    4    5    6    7    8 
Expected Profits   -20   90  -30  -20   80  -70  -60  125 

$ $
If the adversary is awarded the section $1$ through $4$, he will make a net profit of $20$. On the other hand if he is given stations $6, 7$ and $8$, he will make loss of $5$ rupees. This is the best possible value.

-----Input:-----
The first line of the input contains a single integer $N$ indicating the number of stations. The next $N$ lines (lines $2, 3, ..., N+1$) describe the profitability of the $N$ stations. Line $i+1$ contains a single integer denoting the expected profit at station $i$.

-----Output:-----
The first line contains a single integer indicating the minimum possible profit/loss among all segments. The second line contains two integers indicating the starting and ending point of the longest sequence with this minimum profit/loss. If there is more than one answer, it suffices to print one.

-----Constraints:-----
- $1 \leq N \leq 100000$.
- $-10^9 \leq p_i \leq 10^9$

-----Subtasks-----
- Subtask 1 - 40% - $1 \leq N \leq 4000$
- Subtask 2 - 60% - Original constraints

-----Sample Input-----
8
-20
90
-30
-20
80
-70
-60
125

-----Sample Output-----
-5
6 8

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
from bisect import bisect_left as bs
n = int(input())
x = [int(input()) for _ in range(n)]
dp = []
mn = float('inf')
idx = []
mlen = float('-inf')
(si, sj) = (0, 0)
sm = 0

def check(_sm, ind1, ind2, f):
	nonlocal mn, si, sj, mlen
	if _sm < abs(mn) or (_sm == abs(mn) and idx[ind2] - idx[ind1] > mlen):
		(si, sj) = (idx[ind1] + 1, idx[ind2])
		mn = _sm * f
		mlen = sj - si + 1
for (k, v) in enumerate(x, 1):
	sm += v
	ind = bs(dp, sm)
	dp.insert(ind, sm)
	idx.insert(ind, k)
	check(abs(sm), 0, ind, 1)
	if ind > 0:
		prev = ind - 1
		diff = dp[ind] - dp[prev]
		while prev > 0 and dp[ind] - dp[prev - 1] == diff:
			prev -= 1
		check(diff, prev, ind, 1)
	if ind < len(dp) - 1:
		nxt = ind + 1
		diff = dp[nxt] - dp[ind]
		while nxt < len(dp) - 1 and dp[nxt + 1] - dp[ind] == diff:
			nxt += 1
		check(diff, nxt, ind, -1)
print(mn)
print(si, sj)