mehta-and-subarrays

This time your task is simple.

Task:
Mehta has to find the longest subarray whose sum is greater than equal to zero in a given array of length** N**.
After he finds out the length of longest subarray, he has to report how many subarrays of such maximum length exist that satisfy the mentioned property.

Note:
Subarray is defined as an array of contiguous numbers in a particular array.
Subarray(A,B) has length (B-A+1) and consists of all numbers from index A to index B.

Input:
First Line of the input consists of a single integer N as described above.
Next Line consists of N space separated integers.

Output:
In a single line, output the maximum length and number of such subarrays having maximum length separated by a single space.In case, there is no such subarray having sum greater than equal to zero, simply print "-1" without quotes.

Constraints:
N ≤ 10^6
Each number in the array is less than equal to 10^9 and greater than equal to -10^9
(-10^9 ≤ A[i] ≤ 10^9)

SAMPLE INPUT
4
-1 -2 3 -1

SAMPLE OUTPUT
3 2

Source: hackerearth | Difficulty: MEDIUM
Tags: Dynamic programming

Sorting


Solutions: