고전 DP 문제

n행 n열의 격자가 있다. 아르보크는 위에서 i번째 행에 왼쪽부터 $a_i$칸만 남도록 격자의 일부를 잘라냈다. 모든 $i = 1, 2, \ldots, n$에 대해 $a_1 \le a_2 \le \ldots \le a_n$이므로 격자는 영 다이어그램 모양이다. 아르보크는 남은 칸 중 일부에 룩을 놓으려 한다.

룩은 칸 하나를 차지하고, 비어 있는 칸을 몇 칸이든 지나 가로 또는 세로로 움직일 수 있는 기물이다.

칸에 룩이 놓여 있거나, 룩이 한 번의 이동으로 그 칸에 갈 수 있으면 그 칸은 덮인 칸이다.

남은 모든 칸이 덮이도록 놓는 룩의 최소 개수 $r$과, 같은 조건을 만족하도록 룩을 $r$개 놓는 방법의 수 $w$를 구하라. $w$는 998244353으로 나눈 나머지이다.

첫 줄에 격자의 크기 $n$ ($1 \le n \le 5000$)이 주어진다.

둘째 줄에는 아르보크가 남긴 각 행의 너비 $a_1, a_2, \ldots, a_n$ ($1 \le a_1 \le a_2 \le \ldots \le a_n \le n$)이 주어진다.

정수 $r$과 $w$를 출력한다. $r$은 남은 모든 칸을 덮는 데 필요한 룩의 최소 개수이고, $w$는 $r$개의 룩으로 같은 결과를 얻는 배치의 수를 998244353으로 나눈 나머지이다.

첫 번째 예제에서는 룩이 한 개면 모든 칸을 덮을 수 없지만 두 개면 충분하다. 모든 칸을 덮는 두 개의 룩 배치는 여섯 가지이다 (R은 룩, *은 빈 칸을 뜻한다).

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