Maximum Proper Submultiset with Predecessor Constraint

Given a multiset \(S\) (i.e. a collection of elements where repetitions are allowed), select a proper submultiset \(T\) of \(S\) (i.e. \(T \subset S\) and \(T \neq S\)) satisfying the following condition:

For every element \(i \in T\), either \(i\) has no predecessor in \(S\) or the predecessor of \(i\) in \(S\) is also in \(T\). The predecessor of an element \(x\) in \(S\) is defined as the largest element \(y\) in \(S\) such that \(y < x\) (if such a \(y\) exists).

Your task is to choose \(T\) so that its size (i.e. the total number of elements) is maximized. Among all submultisets with the maximum size, choose one for which the sum of its elements is the largest. Then, output the size of \(T\) and the sum of its elements.

Note: Since \(S\) itself always satisfies the condition, you must remove at least one element from \(S\) in order for \(T\) to be a proper subset. When removing exactly one element, note that it is only valid to remove an occurrence of an element \(x\) if doing so does not break the condition. In particular, if \(x\) appears only once in \(S\) and \(x\) is the unique candidate required as the predecessor for some other element, then its removal would force you to also remove those elements. Therefore, a removal of a duplicate occurrence (or the maximum element, which is never used as a predecessor for any element) is always safe.

Formally, if \(S\) consists of \(n\) elements and \(\text{sum}(S)\) is the total sum of all elements, then if you remove an occurrence of some valid candidate \(x\) where the removal is valid and minimal (i.e. only one element is removed), the answer will be:

\[ |T| = n - 1,\quad \text{sum}(T) = \text{sum}(S) - x.\]

Your goal is to choose the candidate \(x\) (among all valid candidates) with the smallest numerical value to maximize \(\text{sum}(T)\) (since subtracting a smaller number yields a larger sum). Note that the minimal element cannot be removed if it is unique, because then elements having that minimal element as a predecessor would violate the condition. In such cases, you must remove an occurrence from a larger value. In summary, if the smallest element appears more than once, remove one occurrence of it; otherwise, remove one occurrence of the smallest possible element that appears at least twice, or if no such element exists (except the maximum), remove one occurrence of the maximum element.

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\) (\(2 \le n \le 10^5\)), representing the number of elements in \(S\).
• The second line contains \(n\) space-separated integers \(s_1, s_2, \dots, s_n\) (each \(1 \le s_i \le 10^9\)), representing the elements of \(S\).

It is guaranteed that \(S\) has at least 2 elements so that a proper subset exists.

outputFormat

Output two space-separated integers on a single line: the size of the chosen submultiset \(T\) and the sum of its elements.

sample

2
1 2

1 1