You are given an array A consisting of n integers. Your task is to divide a subarray A[i,j] into two contiguous parts A[i,k] and A[k+1,j]. Here, any of these parts can be empty.
If S[i,j] denotes the sum of all elements of subarray A[i,j] (the sum of empty sub-array is zero), then X[i,j] denotes the maximum value of abs(S[i,k]−S[k+1,j]) where i−1≤k≤j and abs(Z) is the absolute value of Z.
Note: Sub-array A[i,j] is called empty if i>j
You are required to print the maximum value of X[i,j] where 1≤i≤j≤n.
Input format
Output format
Print an integer that denotes the maximum value of X[i,j].
Constraints
1≤n≤3×105
−109≤A[i]≤109
The maximum value X[i, j] can be obtained for i = 6 and j = 10.
Here if we take k = 8,we get
X[i, j] = abs(S[i, k] - S[k + 1, j])
= abs(S[6, 8] - S[9, 10]) = abs[ (-8 + 5 - 5) - (3 + 8) ]
= abs(-8 - 11) = abs(-19) = 19, which is maximum.