解题思路

设数组重排为 $a'$，定义 $b_i=\mathrm{MEX}(a'_1,\dots,a'_i)$。记多重集合的全局 $\mathrm{mex}$ 为

显然，任何前缀的 $\mathrm{MEX}\le R$，且当已在前缀中出现了 $0,1,\dots,R-1$ 时，$\mathrm{MEX}=R$ 并将一直保持（因为整个数组中没有 $R$）。

题目内容

包含有一个长度为 $n$ 的数组 $a$ 。你可以将 $a$ 任意重排，得到一个新的数组，我们称之为 $a'$。定义一个长度为 $n$ 的数组 $b$，其中 $b_i = MEX(a'_1, a'_2, …, a'_i)$。你需要最大化数组 $b$ 中的元素之和。

你需要输出最大的元素和，以及有多少种可能的重排 $a$，使得 $b$ 中的元素和最大化。由于重排方案数可能很大，你只需要输出其对 $998244353$ 取模后的结果。

【名词解释】

$MEX：$整数数组的 $MEX$ 定义为没有出现在数组中的最小非负整数。例如 $MEX${$1,2,3$}$= 0，MEX${$0,2,5$}$= 1$。

输入描述

第一行输入一个整数 $n (1 ≤ n ≤ 2·10^5)$，表示数组 $a$ 的长度。

第二行输入 $n$ 个整数 $a_1, a_2, …, a_n (0 ≤ a_i ≤ 10^9)$，表示数组 $a$ 的元素。

输出描述

一行输出两个整数，表示 $b$ 的元素和以及 $a$ 的重排数量对 $998244353$ 取模后的结果。

样例1

输入

3
1 0 1

输出

5 1

说明

将 $a$ 重排为 {$0,1,1$} 后，数组 $b$ 为 {$1,2,2$}，元素和为 $5$。可以证明不存在一个重排使得数组 $b$ 的元素和大于 $5$，且仅有这一种重排方案满足条件。