최대 합 순서쌍의 개수

크기가 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