최대 합 순서쌍의 개수

면접 대비

시간 제한1초메모리 제한1024 MB

요약

배열에서 양 끝 원소의 값이 같은 구간 중 합이 가장 큰 구간의 합을 구하고, 그 합을 갖는 구간의 개수를 구합니다.

난이도: 보통10점 중 4점
유형: 해시맵, 누적 합
정답자: 아직 제출이 없습니다

문제

크기가 $N$ 인 배열 $a$ 가 주어진다. 배열의 임의의 위치 $i$ , $j$ 를 골라 아래 두 조건을 모두 만족하면, 같은 수 순서쌍 $(i, j)$ 를 만들 수 있다.

$1 \le i \le j \le N$
$a_i = a_j$

순서쌍 $(i, j)$ 의 합은 $a_i$ 부터 $a_j$ 까지의 합 $a_i + a_{i+1} + \cdots + a_{j-1} + a_j$ 로 정의한다. 주어진 배열에서 만들 수 있는 같은 수 순서쌍 중 합의 최댓값을 구하고, 그 최댓값을 가지는 같은 수 순서쌍의 개수를 세어라.

입력

첫째 줄에 배열 $a$ 의 크기 $N$ 이 주어진다.

둘째 줄에 배열 $a$ 의 원소 $a_1, a_2, \ldots, a_N$ 이 주어진다.

출력

배열에서 만들 수 있는 같은 수 순서쌍의 합의 최댓값과, 그 최댓값을 가지는 같은 수 순서쌍의 개수를 출력한다.

제한

$1 \le N \le 200,000$
$1 \le a_i \le 10^9$

예제2

예제 1
입력
```
6
141 25 69 25 141 7
```
예상 출력
```
401 1
```
예제 2
입력
```
6
3 3 6 2 2 2
```
예상 출력
```
6 3
```