30646번 - 최대 합 순서쌍의 개수

문제

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

• 1 ≤ i ≤ j ≤ N
• a_i = a_j

만들어진 같은 수 순서쌍 (i, j)의 합은 a_i부터 a_j까지의 합 a_i + a_i+1 + a_i+2 + … + a_j-1 + a_j로 정의된다. 이때 주어진 배열에서 만들 수 있는 같은 수 순서쌍의 최대 합을 찾고, 최대 합을 가지는 같은 수 순서쌍의 개수를 출력하는 프로그램을 작성하시오.

입력

첫 번째 배열 a의 크기 N이 주어진다.

두 번째 줄에 배열 a의 원소 a₁, a₂, …, a_N이 주어진다.

출력

주어진 배열에서 만들 수 있는 같은 수 순서쌍의 최대 합과 최대 합을 가진 같은 수 순서쌍의 개수를 출력한다.

제한

• 1 ≤ N ≤ 200,000
• 1 ≤ a_i ≤ 10⁹

힌트