There are N groups students in IIITM each group numbered 1 to n. The ith group contains a[i] number of students.

There are some classroom in IIITM and each classroom has some seats.

All the students of same group have to be in same class and there shouldn't be any seat left.

Moreover group shouldn't change their relative position while taken their seats in class room i.e. group 3 take their seat if and only if group 1 and 2 took their seats.

Find size x of class room and number of class room y such that there is no empty seats in class room (i.e. the total number of student present inside the class room is equal to x)?

Input

The first line contains an integer (1 <= n <= 10^5). The second line contains n space-separated integers a[0], a[1], ... a[n-1] (1 <= a[i] <= 10^4).

Output

Print all possible sizes of the class room in an increasing order with total number of class rooms in new line.

Example:

Input
3
2 2 4

Output
4 2
8 1