P9160 multiset

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

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

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

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