Farmer John は、牛のための新しい大学を開く予定です！

この大学に通う可能性のある牛が $N$ 頭います ($1 \le N \le 10^5$)。各牛が支払ってもよいと考える学費の上限は $c_i$ です ($1 \le c_i \le 10^6$)。Farmer John は、すべての牛が入学するために支払わなければならない学費を設定できます。その学費がある牛の支払い可能な上限を超える場合、その牛は大学に通いません。Farmer John は、教師に公正な賃金を支払えるよう、できるだけ多くのお金を得たいと考えています。得られる最大金額と、設定すべき学費を求めてください。

入力

最初の行には $N$ が与えられます。2 行目には $N$ 個の整数 $c_1, c_2, \dots, c_N$ が与えられ、$c_i$ は牛 $i$ が支払ってもよいと考える学費の上限です。

出力

Farmer John が得られる最大金額と、設定すべき最適な学費を出力してください。解が複数ある場合は、最適な学費が最も小さい解を出力してください。

この問題で扱う整数は大きいため、64 ビット整数型（例えば Java の "long"、C/C++ の "long long"）を使う必要があるかもしれません。

入出力例

入力 1

4
1 6 4 6

出力 1

12 4

注記

Farmer John が学費を $4$ にすると、$3$ 頭の牛が通い、$3 \cdot 4 = 12$ を得られます。

小課題

• テストケース 2 から 4 は $c_i \le 1{,}000$ を満たします。
• テストケース 5 から 8 は $N \le 5{,}000$ を満たします。
• テストケース 9 から 12 には追加の制約はありません。

問題作成：Freddie Tang