Given N pieces of wood, each piece is a rectangle of width 1, and the length of the i^th piece of wood is L_i.

These pieces of wood can be used to make planks. The requirements for making planks are very strict: each plank must also be a rectangle of width 1, and each plank must be formed by splicing exactly two pieces of wood together. The length of a plank made by splicing two pieces of wood of lengths L_i and L_j is L_i + L_j.

The purpose of making planks is to use them to form a fence.

The fence must be composed of several planks of the same length.

The length of the fence is equal to the number of planks used to form the fence, and the height of the fence is equal to the length of each plank in the fence.

We want to use the given wood to make the longest possible fence.

Please determine the maximum possible length of the fence that can be made, and the number of different heights that such a fence of maximum length can have.

Input Format

The first line contains an integer N.

The second line contains N integers L₁, L₂, …, L_N.

Output Format

One line, output two integers, representing the maximum possible length of the fence that can be made, and the number of different heights that such a fence of maximum length can have.

Data Range

2 ≤ N ≤ 10⁶

1 ≤ L_i ≤ 2000

Input Example 1:

4
1 2 3 4

Output Example 1:

2 1

Explanation for Example 1:

The maximum possible length of the fence is 2, meaning it consists of 2 planks. The first plank is made from wood of lengths 1 and 4, and the second plank is made from wood of lengths 2 and 3. The height of the fence is 5, and no other heights are possible.

Input Example 2:

5
1 10 100 1000 2000

Output Example 2:

1 10

Explanation for Example 2:

The maximum possible length of the fence is 1, meaning it consists of 1 plank. In this case, any two pieces of wood can form a plank, resulting in 10 different possible heights: 11, 101, 1001, 2001, 110, 1010, 2010, 1100, 2100, 3000.