Nailed It!

Ο Tudor είναι διαγωνιζόμενος στον Καναδικό Διαγωνισμό Ξυλουργικής (Canadian Carpentry Challenge) (CCC). Για να κερδίσει το CCC, ο Tudor πρέπει να επιδείξει την ικανότητά του στο να καρφώνει ξύλα μεταξύ τους για να φτιάξει τον μακρύτερο δυνατό φράχτη χρησιμοποιώντας σανίδες. Για να να επιτύχει αυτόν τον στόχο, έχει στη διάθεσή του ~N~ κομμάτια ξύλου. Το ~i~-οστό κομμάτι ξύλου έχει ακέραιο μήκος ~L_{i}~.

Μια σανίδα αποτελείται από ακριβώς δύο κομμάτια ξύλου. Το μήκος μιας σανίδας από ξύλα με μήκη ~L_{i}~ και ~L_{j}~ είναι ~L_{i} + L_{j}~. Ένας φράχτης αποτελείται από σανίδες που έχουν το ίδιο μήκος. Το μήκος του φράχτη είναι ο αριθμός των σανίδων που χρησιμοποιούνται για την κατασκευή του, και το ύψος του φράχτη είναι το μήκος κάθε σανίδας του φράχτη. Στο παρακάτω παράδειγμα φράχτη, το μήκος του φράχτη είναι ~4~, το ύψος του φράχτη είναι ~50~ και απεικονίζεται το μήκος κάθε κομματιού ξύλου:

Ο Tudor θα ήθελε να φτιάξει τον μακρύτερο δυνατό φράχτη. Βοηθήστε τον να προσδιορίσει το μέγιστο μήκος οποιουδήποτε φράχτη θα μπορούσε να κατασκευάσει και τον αριθμό των διαφορετικών υψών που θα μπορούσε να έχει ο φράχτης αυτού του μέγιστου μήκους.

Είσοδος

Η πρώτη γραμμή θα περιέχει τον ακέραιο αριθμό ~N\;(2 \le N \le 1000000)~. Η δεύτερη γραμμή θα περιέχει ~N~ ακέραιους αριθμούς ~L_{1}~, ~L_{2}~, ~. . . .~ , ~L_{N}~ ~(1 \le L_{i} \le 2000)~.

Για ~7~ από τους ~15~ διαθέσιμους βαθμούς, ~N \le 100~.

Για επιπλέον ~6~ από τους ~15~ διαθέσιμους βαθμούς, ~N \le 1000~.

Για ~1~ επιπλέον από τους ~15~ διαθέσιμους βαθμούς, ~N \le 100000~.

Έξοδος

Εξάγετε δύο ακέραιους αριθμούς σε μία γραμμή χωρισμένους με ένα κενό: το μήκος του μεγαλύτερου φράχτη και τον αριθμό των διαφορετικών υψών που μπορεί να έχει ο μακρύτερος φράχτης.

Παραδείγματα

input

4
1 2 3 4

output

2 1

Επεξήγηση του πρώτου παραδείγματος:

Ο Tudor συνδυάζει πρώτα τα κομμάτια ξύλου με μήκη ~1~ και ~4~ για να σχηματίσει μια σανίδα μήκους ~5~. Στη συνέχεια συνδυάζει τα κομμάτια ξύλου με μήκη ~2~ και ~3~ για να σχηματίσει άλλη μια σανίδα μήκους ~5~. Τέλος, συνδυάζει τις σανίδες μεταξύ τους για να φτιάξει έναν φράχτη μήκους ~2~ και ύψους ~5~.

input

5
1 10 100 1000 2000

output

1 10

Επεξήγηση του δεύτερου παραδείγματος:

Ο Tudor δεν μπορεί να φτιάξει φράχτη με μήκος μεγαλύτερο από ~1~, και υπάρχουν ~10~ τρόποι για να φτιάξει έναν φράχτη με μήκος ~1~, επιλέγοντας δύο οποιαδήποτε κομμάτια ξύλου για να τα καρφώσει μεταξύ τους. Συγκεκριμένα, μπορεί να έχει έναν φράχτη ύψους ~11~, ~101~, ~1001~, ~2001~, ~110~, ~1010~, ~2010~, ~1100~, ~2100~ και ~3000~.