시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 0 | 0 | 0 | 0.000% |
N개의 정수로 이루어진 수열 A = A0, A1, ..., AN-1이 있다. 부분 수열, 증가 부분 수열, 연속 부분 수열에 대한 정의는 다음과 같다.
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가지가 있으며, 다음과 같다.
수열의 좋음 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)이 주어진다. 둘째 줄에는 a0, a1, ..., an-1이 공백으로 구분되어서 주어진다. (-40 ≤ ai ≤ 40)
총 두 개의 정수를 공백으로 구분해 출력한다. 첫 번째 정수는 입력으로 주어진 수열의 g값이고, 두 번째 정수는 r - l + 1 = m이고, f(l, r) = g인 연속 부분 수열의 개수이다.
3 2 3 1
1 1