You're given an array, you have to split it into sets (possibly empty) such that:
1) The difference between the sizes of these two sets must not exceed 1.
2) The difference between the sum of elements of these two sets should be maximum possible.
The array won’t be given to you at once. Each line contains one integer, you have to add that integer to your current array and then print the new maximised difference of the updated array.
NOTE: Initially the array is empty.
NOTE: Please use fast i/o for solving this problem.
Input Format:
The first line contains integer n (1≤n≤200000). Each of the next n lines contain an Integer i (0≤i≤2∗109)
Output Format:
For each of the n Integers, print the maximised difference of the updated array by including that integer in a new line.
Initially, the array is empty.
Next, the array is: [ 5 ]. Optimal splitting is: { 5 }, { }. Difference between the sums of sets is 5.
Next, array is [ 5, 3 ]. Optimal splitting is { 5 }, { 3 }. Difference between the sums of sets is 2.
Next, the array is: [ 5, 3, 2 ]. Optimal splitting is: { 5, 3 }, { 2 }. Difference between the sums of sets is 6.
Next, the array is: [ 5, 3, 2 ,10 ]. Optimal splitting is: { 5, 10 }, { 3, 2 }. Difference between the sums of sets is 10.
