Histogram Rooks

AtCoder

IDagc041_f

Time4000ms

Memory256MB

Difficulty—

Let us consider a grid of squares with $N$ rows and $N$ columns. Arbok has cut out some part of the grid so that, for each $i = 1, 2, \ldots, N$, the bottommost $h_i$ squares are remaining in the $i$\-th column from the left. Now, he wants to place rooks into some of the remaining squares. A rook is a chess piece that occupies one square and can move horizontally or vertically, through any number of unoccupied squares. A rook can not move through squares that have been cut out by Arbok. Let's say that a square is covered if it either contains a rook, or a rook can be moved to this square in one move. Find the number of ways to place rooks into some of the remaining squares so that every remaining square is covered, modulo $998244353$. ## Constraints * $1 \leq N \leq 400$ * $1 \leq h_i \leq N$ * All input values are integers. ## Input Input is given from Standard Input in the following format: $N$ $h_1$ $h_2$ $...$ $h_N$ [samples]

Samples

Input #1

2
2 2

Output #1

11

Any placement with at least two rooks is fine. There are $11$ such placements.

Input #2

3
2 1 2

Output #2

17

The following $17$ rook placements satisfy the conditions (`R` denotes a rook, `*` denotes an empty square):

R *     * R     * *     R R     R R     R R     
**R     R**     R*R     R**     *R*     **R     


R *     R *     * R     * R     * *     R R     
R*R     *RR     RR*     R*R     RRR     RR*     


R R     R R     R *     * R     R R     
R*R     *RR     RRR     RRR     RRR

Input #3

4
1 2 4 1

Output #3

Input #4

10
4 7 4 8 4 6 8 2 3 6

Output #4

263244071

API Response (JSON)

{
  "problem": {
    "name": "Histogram Rooks",
    "description": {
      "content": "Let us consider a grid of squares with $N$ rows and $N$ columns. Arbok has cut out some part of the grid so that, for each $i = 1, 2, \\ldots, N$, the bottommost $h_i$ squares are remaining in the $i$\\",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc041_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Let us consider a grid of squares with $N$ rows and $N$ columns. Arbok has cut out some part of the grid so that, for each $i = 1, 2, \\ldots, N$, the bottommost $h_i$ squares are remaining in the $i$\\...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments