Description

Given a sequence $B_1,B_2,\dots,B_N$ of length $N$.

An integer $M$ can be represented if and only if you can pick any $K$ numbers $A_1,A_2,\dots,A_K$ from the sequence such that $\sum_{i=1}^{K} A_i = M$.

You need to modify one number $P$ in the sequence so that as many integers as possible can be represented.

Input Format

The first line contains an integer $N$.

The second line contains $N$ integers $B_1,B_2,\dots,B_N$.

Output Format

Output one line with two integers $P,Q$, separated by a space.

This means changing a number $P$ in the sequence to $Q$.

If there are multiple solutions, output the smallest possible $P$. If there are still multiple solutions when $P$ is minimized, output the smallest possible $Q$.

4
1 3 4 4

4 9

5
3 3 3 3 3

3 1

Hint

For $100\%$ of the testdata, it is guaranteed that $2 \le N \le 100$ and $1 \le B_i \le 7000$.

This problem is translated from BalticOI 2010 Day2 T2 Candies。

Translated by ChatGPT 5