Bessie e Canmuu hanno trovato un sacco di $N$ monete d'oro ($1 \leq N \leq 250$), da dividere il più equamente possibile. La moneta $i$ vale $v_i$ ($1 \leq V_i \leq 2{,}000$). Le mucche vorrebbero due mucchi uguali, ma non sempre è possibile. Qual è la minima differenza di valore?

Più divisioni possono ottenere tale differenza minima. Vogliono anche contare le divisioni più giuste. Se non si può dividere equamente, Bessie riceve il mucchio di maggior valore.

Per esempio, cinque monete valgono $2, 1, 8, 4, 16$. Un mucchio ha quella da $16$, l'altro le restanti per $1+2+4+8=15$. La differenza è $16-15 = 1$. È l'unica divisione così, quindi il numero di divisioni più eque è $1$.

Scambiare monete di uguale valore tra i mucchi aumenta le divisioni ottimali. Così $\{1, 1, 1, 1\}$ ha sei divisioni ottimali distinte, con due monete per mucchio.

Input

Leggi dall'input standard.

• Riga $1$: un intero $N$.

• Righe $2..N+1$: la riga $i+1$ contiene un intero $V_i$.

Output

Scrivi sull'output standard.

• Riga $1$: un intero, la minima differenza dei valori dei mucchi.

• Riga $2$: numero di divisioni con la differenza minima della prima riga. Può essere grande; stampa il resto della divisione per $1,000,000$.

Esempi

Input 1

5
2
1
8
4
16

Output 1

1
1

Crediti: Sherry Wu, un classico, 2010