14879번 - 수열의 좋음

N개의 정수로 이루어진 수열 A = A₀, A₁, ..., A_N-1이 있다. 부분 수열, 증가 부분 수열, 연속 부분 수열에 대한 정의는 다음과 같다.

• 부분 수열: 수열 A에서 0개 또는 그 이상의 수를 지워서 만들 수 있는 수열. 이때, 지워지지 않은 수의 순서를 바꾸면 안 된다. 부분 수열의 크기는 0일 수 있으며, 이때는 비어있는 부분 수열이라고 부른다.
• 증가 부분 수열: 길이가 0보다 큰 부분 수열 중에서, 각각의 수가 앞에 있는 수보다 커야한다.
• 연속 부분 수열: 부분 수열 중에서, 지워지지 않은 수가 원래 수열 A에서 연속되어 있는 경우를 의미한다. A의 l번째 수부터 r번째 수까지로 이루어진 연속 부분 수열은 A[l, r](= A_l, A_l+1, ..., A_r)로 표현한다. (l ≤ 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]이 있다.

수열에서 정의할 수 있는 함수는 총 3가지가 있으며, 다음과 같다.

• sum(l, r) = A_l + A_l+1 + ... + A_r
• inc(l, r) = A[l, r]의 증가 부분 수열 중에서, 수열에 포함된 수의 합이 가장 큰 합
• f(l, r) = sum(l, r) - inc(l, r)

수열의 좋음 g는 다음과 같이 정의할 수 있다.

g = max(f(l, r)) (0 ≤ l ≤ r < n)

즉, g는 A의 모든 연속 부분 수열의 f(l, r) 중에서 가장 큰 값이다.

정수 m을 f(l, r) = g인 가장 작은 연속 부분 수열의 길이라고 하자.

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

첫째 줄에 정수 n(1 ≤ n ≤ 200,000)이 주어진다. 둘째 줄에는 a₀, a₁, ..., a_n-1이 공백으로 구분되어서 주어진다. (-40 ≤ a_i ≤ 40)

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