A non-empty zero-indexed array A of N integers is given. A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a

*slice*of array A. The*sum*of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].
A

*min abs slice*is a slice whose absolute sum is minimal.
For example, array A such that:

`A[0] = 2 A[1] = -4 A[2] = 6 A[3] = -3 A[4] = 9`

contains the following slices, among others:

- (0, 1), whose absolute sum = |2 + (−4)| = 2
- (0, 2), whose absolute sum = |2 + (−4) + 6| = 4
- (0, 3), whose absolute sum = |2 + (−4) + 6 + (−3)| = 1
- (1, 3), whose absolute sum = |(−4) + 6 + (−3)| = 1
- (1, 4), whose absolute sum = |(−4) + 6 + (−3) + 9| = 8
- (4, 4), whose absolute sum = |9| = 9

Both slices (0, 3) and (1, 3) are min abs slices and their absolute sum equals 1.

Write a function:

int solution(int A[], int N);

that, given a non-empty zero-indexed array A consisting of N integers, returns the absolute sum of min abs slice.

For example, given:

`A[0] = 2 A[1] = -4 A[2] = 6 A[3] = -3 A[4] = 9`

the function should return 1, as explained above.

Assume that:

- N is an integer within the range [1..100,000];
- each element of array A is an integer within the range [−10,000..10,000].

Complexity:

- expected worst-case time complexity is O(N*log(N));
- expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).