Background

ZHY has many sets. When there are many sets, they become a multiset.

Problem Description

Given a multiset (elements in the set may repeat) $S$, find the largest multiset $T$ such that $T$ is a proper subset of $S$, and for every element $i$ in $T$, either $i$ has no predecessor in $S$, or the predecessor of $i$ in $S$ $\in T$. If there are multiple sets with the same maximum size that satisfy the conditions, then choose the one with the largest sum of all elements. Output the size of $T$ and the sum of its elements.

The predecessor of a number $x$ in a set $S$ is defined as the maximum element $y$ among all elements in $S$ with $y < x$.

Input Format

The first line contains a positive integer $n$, representing the size of $S$.

The second line contains $n$ positive integers, representing the elements in $S$.

Output Format

Output one line with two integers. The first number is the size of $T$, and the second number is the sum of all elements in $T$.

4
4 5 1 4

3 10

6
1 4 2 8 5 7

5 19

Hint

Sample 1 Explanation

$T$ is $\{5,1,4\}$.

Sample 2 Explanation

$T$ is $\{1,4,2,5,7\}$.

Constraints

For $30\%$ of the testdata, $n \le 15$.

For $100\%$ of the testdata, $2 \le n \le 10^5$, and $1 \le$ elements in $S \le 10^9$.

Translated by ChatGPT 5