Delete Range Mex

AtCoder

IDarc178_d

Time2000ms

Memory256MB

Difficulty—

You are given a positive integer $N$ and a sequence of $M$ non-negative integers $A = (A_{1}, A_{2}, \dots, A_{M})$. Here, all elements of $A$ are distinct integers between $0$ and $N-1$, inclusive. Find the number, modulo $998244353$, of permutations $P$ of $(0, 1, \dots, N-1)$ that satisfy the following condition. * After initializing a sequence $B = (B_{1}, B_{2}, \dots, B_{N})$ to $P$, it is possible to make $B = A$ by repeating the following operation some number of times: * Choose $l$ and $r$ such that $1 \leq l \leq r \leq |B|$, and if $\mathrm{mex}({B_{l}, B_{l+1}, \dots, B_{r}})$ is contained in $B$, remove it from $B$. What is $\mathrm{mex}(X)$? For a finite set $X$ of non-negative integers, $\mathrm{mex}(X)$ is defined as the smallest non-negative integer that is not in $X$. ## Constraints * $1 \leq M \leq N \leq 500$ * $0 \leq A_{i} < N$ * All elements of $A$ are distinct. * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $M$ $A_{1}$ $A_{2}$ $\cdots$ $A_{M}$ [samples]

Samples

Input #1

4 2
1 3

Output #1

8

After initializing $B = (2, 1, 0, 3)$, it is possible to make $B = A$ using the following steps:

*   Choose $(l, r) = (2, 4)$, remove $\mathrm{mex}({1, 0, 3}) = 2$ from $B$, making $B = (1, 0, 3)$.
*   Choose $(l, r) = (3, 3)$, remove $\mathrm{mex}({3}) = 0$ from $B$, making $B = (1, 3)$.

Thus, $P = (2, 1, 0, 3)$ satisfies the condition.
There are eight permutations $P$ that satisfy the condition, including the above, so print $8$.

Input #2

4 4
0 3 2 1

Output #2

1

Only $P = (0, 3, 2, 1)$ satisfies the condition.

Input #3

16 7
9 2 4 0 1 6 7

Output #3

Input #4

92 4
1 67 16 7

Output #4

726870122

Find the count modulo $998244353$.

API Response (JSON)

{
  "problem": {
    "name": "Delete Range Mex",
    "description": {
      "content": "You are given a positive integer $N$ and a sequence of $M$ non-negative integers $A = (A_{1}, A_{2}, \\dots, A_{M})$. Here, all elements of $A$ are distinct integers between $0$ and $N-1$, inclusive. F",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc178_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a positive integer $N$ and a sequence of $M$ non-negative integers $A = (A_{1}, A_{2}, \\dots, A_{M})$.\nHere, all elements of $A$ are distinct integers between $0$ and $N-1$, inclusive.\nF...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments