정수로 이루어진 수열이 주어진다.

연속 부분 수열이란, 수열에서 차례대로 나열된 1개 이상의 수를 연속해서 고른 것이다.

예를 들어 다음 수열이 있다고 하자.

1 2 -3 4 5 4 3 2 1 -6

이 수열에서 4 5 4 3 2 1은 연속 부분 수열이다.

각 연속 부분 수열의 합을 구했을 때, 그중 가장 큰 값을 최대 연속 부분 수열 합이라고 한다.

수열이 주어졌을 때, 최대 연속 부분 수열 합과 그 합을 가지는 연속 부분 수열의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 n이 입력된다.

둘째 줄에 n개의 정수 c1, c2, ... , cn이 공백으로 구분되어 입력된다.

출력

최대 연속 부분 수열 합과 그 합을 가지는 연속 부분 수열의 개수를 공백으로 구분하여 출력한다.

제한

• 1 <= n <= 3000
• -100000 <= ci <= 100000

예제 입력 1

10
1 2 -3 4 5 4 3 2 1 -6

예제 출력 1

19 2

예제 1 설명

주어진 수열에서 연속 부분 수열의 합이 가장 큰 값은 19이다.

합이 19가 되는 연속 부분 수열은 다음 2개이다.

• 1번째 수부터 9번째 수까지의 연속 부분 수열
• 4번째 수부터 9번째 수까지의 연속 부분 수열

따라서 19 2를 출력한다.