P8587 New Hometown

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.

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?

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 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.

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