Pregue!

Tudor é um competidor na Competição de Carpintaria Canadense (CCC). Para vencer a CCC, Tudor deve demonstrar sua habilidade em pregar tábuas de madeira para fazer a cerca mais longa possível. Para alcançar esse objetivo, ele possui NN peças de madeira. A i-ésima peça de madeira tem comprimento inteiro LiL_i.

Uma tábua é feita exatamente com duas peças de madeira. O comprimento de uma tábua feita de madeiras com comprimentos LiL_i e LjL_j é Li+LjL_i + L_j. Uma cerca consiste em tábuas que têm o mesmo comprimento. O comprimento da cerca é o número de tábuas usadas para construí-la, e a altura da cerca é o comprimento de cada tábua na cerca. No exemplo de cerca abaixo, o comprimento da cerca é 44; a altura da cerca é 5050; e o comprimento de cada peça de madeira é mostrado:

Figura 1

Tudor gostaria de fazer a cerca mais longa possível. Por favor, ajude-o a determinar o comprimento máximo de qualquer cerca que ele poderia fazer, e o número de alturas diferentes que uma cerca desse comprimento máximo poderia ter.

Entrada

A primeira linha conterá o inteiro N (2N1 000 000)N \ (2 \leq N \leq 1 \ 000 \ 000).

A segunda linha conterá NN inteiros separados por espaço L1, L2,...,LN (1Li2 000)L_1, \ L_2, . . . , L_N \ (1 \leq L_i \leq 2 \ 000).

Saída

Imprima dois inteiros em uma única linha separados por um único espaço: o comprimento da cerca mais longa e o número de alturas diferentes que uma cerca com o comprimento máximo poderia ter.

Explicação Exemplo de Entrada/Saída 1:

Tudor primeiro combina as peças de madeira com comprimentos 11 e 44 para formar uma tábua de comprimento 55. Então ele combina as peças de madeira com comprimentos 22 e 33 para formar outra tábua de comprimento 55. Finalmente, ele combina as tábuas para fazer uma cerca com comprimento 22 e altura 55.

Explicação Exemplo de Entrada/Saída 2:

Tudor não pode fazer uma cerca com comprimento maior que 11, e existem 1010 formas de fazer uma cerca com comprimento 11, escolhendo qualquer duas peças de madeira para pregar juntas. Especificamente, ele pode ter uma cerca com altura 11, 101, 1001, 2001, 110, 1010, 2010, 1100, 210011, \ 101, \ 1001, \ 2001, \ 110, \ 1010, \ 2010, \ 1100, \ 2100 e 30003000.

Exemplos de Entrada Exemplos de Saída
4
1 2 3 4
2 1
5
1 10 100 1000 2000
1 10