시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB273342.857%

문제

체육 시간이 되어 $N$명의 학생들이 운동장에 서 있다. 선생님 정원이는 학생들을 키 순서대로 정렬하려고 한다. 현재 학생들은 줄 A에 서 있는데, 정원이는 다음과 같은 방식으로 학생들을 줄 B로 옮기려고 한다.

  1. 정원이가 줄 A에 있는 학생 중 맨 앞에 있는 $1$명 이상의 학생을 임시 줄로 옮긴다.
  2. 임시 줄에 있는 학생들을 키의 오름차순으로 정렬한다. 정렬 후 가장 키가 작은 학생이 맨 앞에 있다.
  3. 임시 줄에 있는 모든 학생들을 줄 B의 뒤쪽으로 순서를 바꾸지 않고 옮긴다.
  4. 줄 A에 학생이 모두 없어질 때까지 1 ~ 3단계를 반복한다.

정원이는 줄 A에 있는 학생들을 옮기는 방법을 바꾸면 줄 B로 이동하는 학생들의 최종 순서가 바뀔 수 있다는 것을 확인하였다. 정원이는 학생들의 최종 순서로 가능한 경우가 얼마나 있는지 알아보려고 한다. 학생들의 가능한 최종 순서의 가짓수를 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에 학생의 수 $N$이 주어진다.

두 번째 줄에는 학생들의 키 순서를 나타내는 정수 $N$개가 주어진다. $i+1$($0 \leq i < N$)번째 값은 앞에서 $i+1$번째 학생보다 키가 작은 학생 수를 의미하는 $0$ 이상 $N-1$ 이하의 정수이다. 모든 학생의 키는 서로 다르다.

출력

정원이가 학생들을 모두 정렬한 다음 나올 수 있는 학생들의 순서로 가능한 경우의 수를 $998\,244\,353$으로 나눈 나머지를 출력한다.

서브태스크

모든 데이터에 대해서, $1 \leq N \leq 250\,000$ 를 만족한다.

번호배점제한
11

$N ≤ 16$

21

$N ≤ 250$

31

추가 제약조건은 없다.

예제 입력 1

5
0 2 1 3 4

예제 출력 1

2

예제 입력 2

6
5 4 3 2 1 0

예제 출력 2

32

예제 입력 3

9
6 7 8 3 4 5 0 1 2

예제 출력 3

55

출처

Contest > BOJ User Contest > FunctionCup > FunctionCup 2023 QR번

채점 및 기타 정보

  • 예제는 채점하지 않는다.