考虑一个 $n$ 行 $n$ 列的网格。Arbok 剪掉了一部分网格，使得对于每个 $i = 1, 2, \dots, n$，第 $i$ 行（从上往下数）仅剩下最左侧的 $a_i$ 个方格。这些 $a_i$ 的值满足 $a_1 \le a_2 \le \dots \le a_n$，即该网格形状类似于一个杨图（Young diagram）。现在，Arbok 想要在剩余的方格中放置一些车。

车是一种国际象棋棋子，占据一个方格，可以水平或垂直移动经过任意数量的空格。

如果一个方格内放置了车，或者车可以通过一次移动到达该方格，则称该方格被覆盖。

求 Arbok 为了覆盖所有剩余方格所需放置的最少车数 $r$，以及放置 $r$ 个车以满足该条件的方案数 $w$，结果对 $998\,244\,353$ 取模。

输入格式

第一行包含一个整数 $n$，表示网格的大小 ($1 \le n < 2^{17}$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示 Arbok 留下的各行宽度 ($1 \le a_1 \le a_2 \le \dots \le a_n \le n$)。

输出格式

输出两个整数 $r$ 和 $w$，分别表示覆盖所有剩余方格所需的最少车数，以及放置 $r$ 个车以满足该条件的方案数，结果对 $998\,244\,353$ 取模。

样例

样例输入 1

3
1 2 3

样例输出 1

2 6

说明

在第一个样例测试中，一个车不足以覆盖所有方格，但两个车足够了。共有六种放置两个车以覆盖所有方格的方案（R 表示车，* 表示空方格）：

R * * * * *
** R* R* R* *R **
*R* R** *R* **R R** RR*