고전적인 FFT 문제

행과 열이 각각 $n$개인 격자판이 있습니다. Arbok은 위에서 $i$번째 행 ($1 \le i \le n$)에서 왼쪽 $a_i$칸만 남도록 격자판의 일부를 잘라냈습니다. $a_1 \le a_2 \le \ldots \le a_n$이므로 격자판은 영 다이어그램(Young diagram) 모양입니다. Arbok은 남은 칸 중 일부에 룩(rook)을 놓으려 합니다.

룩은 한 칸을 차지하며, 빈 칸을 건너 가로나 세로 방향으로 몇 칸이든 이동할 수 있습니다.

어떤 칸에 룩이 놓여 있거나, 룩이 한 번의 이동으로 그 칸에 도달할 수 있으면 그 칸은 덮인 칸입니다.

남은 모든 칸이 덮이도록 룩을 놓을 때 필요한 최소 룩의 개수 $r$과, 같은 조건을 만족하면서 $r$개의 룩을 놓는 방법의 수 $w$를 구하세요. $w$는 $998\,244\,353$으로 나눈 나머지입니다.

첫 줄에 격자판의 크기 $n$이 주어집니다 ($1 \le n < 2^{17}$).

둘째 줄에는 Arbok이 남긴 각 행의 너비 $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$개의 룩으로 그렇게 하는 방법의 수를 $998\,244\,353$으로 나눈 나머지입니다.

첫 번째 입력 예시에서는 룩 한 개로 모든 칸을 덮을 수 없지만, 룩 두 개면 충분합니다. 모든 칸을 덮는 룩 두 개의 배치는 6가지이며 다음과 같습니다 (R은 룩, *은 빈 칸):

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