Universal Cup Judging System

Universal Cup

حد الوقت: 3.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

$\{1, 2, \dots, N\}$의 순열 $P$가 주어집니다.

즉, $P$는 $1$부터 $N$까지의 모든 정수를 정확히 한 번씩 포함하는 길이가 $N$인 배열입니다.

이 배열에 대해 다음 연산을 수행할 수 있습니다:

  • 인덱스 $i$($1 < i < |P|$)를 선택합니다.
  • $P_i = \max(P_{i-1}, P_i, P_{i+1})$로 설정합니다.
  • $P$에서 $P_{i-1}$과 $P_{i+1}$을 삭제합니다. 남은 원소들은 다시 $1$부터 시작하도록 인덱스가 재부여됩니다.

이러한 연산을 한 번 수행할 때마다 $P$의 길이는 $2$씩 줄어듭니다. 특히, $P$의 길이가 $1$ 또는 $2$이면 이 연산을 적용할 수 없습니다.

$P$에서 시작하여 이 연산을 0번 이상 수행함으로써 도달할 수 있는 서로 다른 배열의 개수를 구하세요.

이 값은 매우 클 수 있으므로 $998\,244\,353$으로 나눈 나머지만 구하면 됩니다.

입력

입력은 다음 형식으로 주어집니다:

T
N
P_1 P_2 ... P_N
...

제약 조건

  • 모든 입력값은 정수입니다.
  • $1 \le T \le 10^5$
  • $1 \le N \le 5000$
  • $1 \le P_i \le N$
  • 모든 $i \ne j$에 대해 $P_i \ne P_j$입니다.
  • 모든 테스트 케이스에서 $N^2$의 합은 $5000^2$을 초과하지 않음이 보장됩니다.

출력

각 테스트 케이스에 대해, $P$에 연산을 0번 이상 수행하여 도달할 수 있는 서로 다른 배열의 개수를 $998\,244\,353$으로 나눈 나머지를 하나의 정수로 출력합니다.

예제

예제 입력 1

5
2
2 1
3
2 1 3
5
3 1 4 5 2
10
1 2 3 4 5 6 7 8 9 10
15
5 7 6 12 2 13 10 1 11 4 3 9 14 15 8

예제 출력 1

1
2
5
55
365

노트

테스트 케이스 1: 어떤 연산도 수행할 수 없습니다.

테스트 케이스 2: 두 가지 가능성이 있습니다:

  • 아무 연산도 수행하지 않습니다. 최종 배열은 $[2, 1, 3]$입니다.
  • $i = 2$로 연산을 한 번 수행합니다. 최종 배열은 $[3]$입니다.

도달 가능한 배열은 이뿐입니다.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.