Background

In the year 2102, the ecosystem of the Solar System can finally no longer support human survival. Humans plan to travel along the interstellar long-distance route built earlier to a planet $\beta$ in the Taurus Crab Nebula to seek development.

Problem Description

As one of the first group of researchers, you arrived on planet $\beta$ in advance to build a base.

Planet $\beta$ is rich in manganese-titanium ore. The base needs some pillars of the same height, and each pillar must be formed by connecting exactly two pieces of manganese-titanium ore in sequence. For example, if you have two pieces of ore with heights $h_x, h_y$, then you can combine them into one pillar of height $h_x + h_y$. Each piece of ore can obviously be used at most once.

Now you have arrived at the manganese-titanium mine on planet $\beta$. In front of you are $n$ pieces of ore with heights $h_i$. After careful thinking, you realize that the sturdiness of the houses should depend on the number of pillars, not their height. So you want to know: using these $n$ ores, what is the maximum number of pillars with the same height that can be built?

But Xiaohua thinks this problem is too easy, so they ask you one more thing: suppose all pillars have height $h$, and the base can build at most $\mathrm{res}$ pillars. Then, when the number of pillars is also $\mathrm{res}$, how many different values can $h$ take?

Input Format

The input consists of two lines.

The first line contains one positive integer $n$, representing the number of manganese-titanium ore pieces.

The second line contains $n$ positive integers $h_i$, with the meaning described above.

Output Format

Output one line containing two integers $\mathrm{res}$ and $\mathrm{ans}$, representing the maximum number of pillars and, under this optimal value, how many different height choices there are.

4
4 7 6 5

2 1

6
1 1000 100 1500 10 1800

1 15

Hint

Additional samples are provided in the attachment ex.in/out.

Constraints:

For $20\%$ of the testdata, $1 \leq n \leq 100$.

For $40\%$ of the testdata, $1 \leq n \leq 10^3$.

For $70\%$ of the testdata, $1 \leq n \leq 10^5$.

For $100\%$ of the testdata, $1 \leq n \leq 10^6$, and $1 \leq h_i \leq 3 \times 10^3$.

Translated by ChatGPT 5