수열의 좋음

정수 $N$개로 이루어진 수열 $A = A_0, A_1, \dots, A_{N-1}$이 있다. 부분 수열, 증가 부분 수열, 연속 부분 수열의 정의는 다음과 같다.

• 부분 수열: 수열 $A$에서 $0$개 이상의 수를 지워서 만드는 수열. 지우지 않은 수의 순서는 바꾸지 않는다. 크기가 $0$인 부분 수열도 있으며, 이를 빈 부분 수열이라고 한다.
• 증가 부분 수열: 길이가 $1$ 이상인 부분 수열 중에서, 각각의 수가 바로 앞의 수보다 큰 것.
• 연속 부분 수열: 지우지 않은 수가 원래 수열 $A$에서 서로 이웃한 부분 수열. $A$의 $l$번째 수부터 $r$번째 수까지로 이루어진 연속 부분 수열을 $A[l, r] = A_l, A_{l+1}, \dots, A_r$로 쓴다. ($l \le r$)

$A = [2, 1, 3]$이면 부분 수열은 $[], [2], [1], [3], [2, 1], [2, 3], [1, 3], [2, 1, 3]$이고, 연속 부분 수열은 $[2], [1], [3], [2, 1], [1, 3], [2, 1, 3]$이며, 증가 부분 수열은 $[2], [1], [3], [2, 3], [1, 3]$이다.

수열에서 정의하는 함수는 다음 세 가지다.

• $sum(l, r) = A_l + A_{l+1} + \dots + A_r$
• $inc(l, r)$: $A[l, r]$의 증가 부분 수열 중에서 원소의 합이 가장 큰 값
• $f(l, r) = sum(l, r) - inc(l, r)$

수열의 좋음 $g$는 $g = \max f(l, r)$ ($0 \le l \le r < N$)로 정의한다. 즉 $g$는 $A$의 모든 연속 부분 수열의 $f(l, r)$ 중 가장 큰 값이다.

정수 $m$은 $f(l, r) = g$인 연속 부분 수열의 길이 중 가장 작은 값이다.

$A$가 주어졌을 때 먼저 $g$를 구하고, $r - l + 1 = m$이면서 $f(l, r) = g$인 연속 부분 수열의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 정수 $N$ ($1 \le N \le 200{,}000$)이 주어진다. 둘째 줄에 $A_0, A_1, \dots, A_{N-1}$이 공백으로 구분되어 주어진다. ($-40 \le A_i \le 40$)

정수 두 개를 공백으로 구분해 한 줄에 출력한다. 첫 번째 정수는 주어진 수열의 $g$이고, 두 번째 정수는 $r - l + 1 = m$이면서 $f(l, r) = g$인 연속 부분 수열의 개수이다.