최대 합 순서쌍의 개수
시간 제한1초메모리 제한1024 MB
양 끝 값이 같은 모든 순서쌍 (i, j) 중 구간 합이 최대인 것을 찾고, 그 최댓값을 갖는 순서쌍의 개수를 센다.
문제
크기가 N인 배열 a가 주어진다. 배열 a의 임의의 위치를 나타내는 두 수 i, j를 골랐을 때, 아래 두 조건을 만족하면 같은 수 순서쌍 (i, j)를 만들 수 있다.
- 1 ≤ i ≤ j ≤ N
- ai = aj
만들어진 같은 수 순서쌍 (i, j)의 합은 ai부터 aj까지의 합 ai + ai+1 + ai+2 + … + aj-1 + aj로 정의된다. 이때 주어진 배열에서 만들 수 있는 같은 수 순서쌍의 최대 합을 찾고, 최대 합을 가지는 같은 수 순서쌍의 개수를 출력하는 프로그램을 작성하시오.
입력
첫 번째 배열 a의 크기 N이 주어진다.
두 번째 줄에 배열 a의 원소 a1, a2, …, aN이 주어진다.
출력
주어진 배열에서 만들 수 있는 같은 수 순서쌍의 최대 합과 최대 합을 가진 같은 수 순서쌍의 개수를 출력한다.
제한
- 1 ≤ N ≤ 200,000
- 1 ≤ ai ≤ 109