1432 . 排隊
TopCoder
Tags
Description
今天是長頸鹿大學的畢業典禮，而現在正是拍團體照的時間。今年一共有 $n$ 個畢業生，每個畢業生的身高皆為介於 $1$ 到 $n$ 的正整數，且任兩個畢業生的身高皆不相同。
為了拍出好看的照片，老師們打算先讓畢業生們排成一排再指揮他們移動到拍照的場所，然而在老師們指揮其中 $m$ 個畢業生排進隊伍後，他們才意識到要讓畢業生的身高由小到大排才會是正確的！但由於時間緊急他們沒空重新排隊伍，於是對於剩下的畢業生，老師們決定將他們插入在一個「附近的身高看起來是遞增的」位置。具體來說，一個身高為 $x$ 的畢業生插入的位置需要滿足以下條件之一：
- 插入的位置為隊伍最前面且 $x$ 小於他後面的人的身高。
- 插入的位置為隊伍最後面且 $x$ 大於他前面的人的身高。
- 插入的位置不是隊伍最前面或最後面、$x$ 小於他後面的人的身高且 $x$ 大於他前面的人的身高。
舉例來說，若目前隊伍的身高依序為 $[3, 5, 2]$，那麼一個身高為 $4$ 的畢業生可以插入 $3$ 跟 $5$ 之間，或是插入隊伍最後面。但是不能插入隊伍最前面或是 $5$ 跟 $2$ 之間。
現在給定目前隊伍的樣子以及剩下還沒進入隊伍的 $n - m$ 個人插入隊伍的順序，你能幫幫老師們計算最後隊伍的樣子會有幾種嗎？由於數量很多，請輸出答案取模 $998244353$。兩個隊伍不同代表存在一個位置兩個人的身高不一樣。
Input Format
輸入第一行有兩個正整數 $n, m$，代表畢業生的數量以及目前已經進入隊伍的畢業生數量。
輸入第二行有 $m$ 個正整數 $a_1, a_2, \ldots, a_m$，其中 $a_i$ 代表目前隊伍第 $i$ 個人的身高。
輸入第三行有 $n - m$ 個正整數 $b_1, b_2, \ldots, b_{n - m}$，其中 $b_i$ 代表第 $i$ 個插入隊伍的人的身高。
- $2 \leq n \leq 2 \times 10^ 5$
- $1 \leq m < n$
- $1 \leq a_i, b_i \leq n$
- 所有 $a_1, a_2, \ldots, a_m, b_1, b_2, \ldots, b_{n - m}$ 皆不一樣。
Output Format
輸出一行，該行有一個整數代表答案。請記得要對 $998244353$ 取模。
Sample Input 1
7 4 1 5 2 6 4 3 7
Sample Output 1
4
Sample Input 2
5 3 1 3 4 5 2
Sample Output 2
1
Hints
第一筆範例測資中，一共有 $4$ 種可能的最後的隊伍：
- $[1, 3, 5, 2, 4, 6, 7]$
- $[1, 5, 2, 3, 4, 6, 7]$
- $[1, 4, 5, 2, 3, 6, 7]$
- $[1, 3, 4, 5, 2, 6, 7]$
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資。 | 0 |
| 2 | 0~11 | 無額外限制。 | 100 |