3

연결시켜 붙이기

시간제한 : 2초

경곽이는 ACM-ICPC 참가자이다. 대회에서 우승하기 위해 경곽이는 주어진 판자들을 이용해 만들 수 있는 담장의 최대 길이를 알아내야 한다.

n개의 판자 조각이 주어졌을 때, 담장을 만들 수 있는 단위 길이는 정확히 2개의 판을 이어 붙여 만들고, 그렇게 만든 것들을 연결해 붙인 담장의 높이는 모두 같아야한다. 담장의 길이는 담장을 만들기 위해 사용된 단위 길이의 개수를 의미하고, 담장의 높이는 단위 길이의 높이이다.

예를 들어, 아래 그림은 길이가 4, 높이가 50인 담장의 예이다.

각 판자의 크기	20	40	30	15	담장의 높이 50
				35
	30
			20
		10
	담장의 길이 4

n개의 판자 조각이 주어졌을 때 만들 수 있는 가장 긴 담장 길이와, 그러한 길이가 가능한 높이의 가짓수를 구해보자.

입력형식

첫 줄에는 사용할 수 있는 판자의 개수(n)가 입력된다.([eqn: 2 LEQ n LEQ `1,000,000])

두 번째 줄에는 각 판자의 크기(높이, Li)가 공백을 두고 입력된다.([eqn: 1 LEQ `L _{i} `` LEQ `2,000])

출력형식

가능한 최대 길이와 그 길이로 만들 수 있는 높이의 가짓수를 공백을 두고 출력한다.

입출력 예시

입력1

4

1 2 3 4

출력1

2 1

설명 (1+4), (2+3) 으로 길이 2짜리 담장을 만들 수 있고, 높이는 5가 유일하다.

입력2

5

1 10 100 1000 2000

출력2

1 10

5개 중 2개만 골라 길이 1짜리 담장을 만들 수 있고,

높이는 11, 101, 1001, 2001, 110, 1010, 2010, 1100, 2100, 3000이 가능하다.