考虑一个 $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 \le 5000$)。

第二行包含 $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*