C - Buildings Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 800 点

問題文

2 以上の整数 N と N-1 個の整数 C_1,C_2,\dots ,C_{N-1} が与えられます.

N 個の建物が数直線上に一列に並んでいます. i 個目の建物は位置 i に建っており，高さは H_i です. ここで (H_1,H_2,\dots ,H_N) は (1,2,\dots ,N) の順列であることが分かっていますが，具体的な H_1,H_2,\dots ,H_N は分かっていません.

次の条件が x=1,2,\dots, N-1 のすべてについて成り立つような (H_1,H_2,\dots, H_N) としてあり得るものの個数を 998244353 で割ったあまりを求めてください.

  • 位置 x+0.5 から見える建物の個数は C_x 個である. ここで，i 番目の建物が見えるのは，位置 x+0.5 と位置 i の間に H_i より高さが高い建物が存在しないとき，またそのときに限る.

制約

  • 2\le N\le 2\times 10^5
  • 1\le C_x\le N
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる.

N
C_1 C_2 \dots C_{N-1}

出力

答えを出力せよ.

入力例 1

4
2 2 3

出力例 1

3

たとえば，(H_1,H_2,H_3,H_4)=(3,4,2,1) は条件を満たします. 実際，

  • x=1 について，位置 x+0.5=1.5 から見える建物は 1,2 個目の建物で，あわせて 2=C_1 個
  • x=2 について，位置 x+0.5=2.5 から見える建物は 2,3 個目の建物で，あわせて 2=C_2 個
  • x=3 について，位置 x+0.5=3.5 から見える建物は 2,3,4 個目の建物で，あわせて 3=C_3 個

となります. 条件を満たす (H_1,H_2,H_3,H_4) はこれを含めて 3 通りあります.

入力例 2

3
2 1

出力例 2

0

条件を満たす (H_1,H_2,\dots, H_N) が存在しないこともあります.

入力例 3

7
3 3 3 3 4 4

出力例 3

85

Score : 800 points

Problem Statement

You are given an integer N that is at least 2, and N-1 integers C_1,C_2,\dots ,C_{N-1}.

There are N buildings lined up on a number line. The i-th building stands at position i and has height H_i. It is known that (H_1,H_2,\dots ,H_N) is a permutation of (1,2,\dots ,N), but the specific values of H_1,H_2,\dots ,H_N are not known.

Find the number, modulo 998244353, of possible sequences (H_1,H_2,\dots, H_N) such that the following condition holds for all of x=1,2,\dots, N-1.

  • The number of buildings visible from position x+0.5 is C_x. Here, the i-th building is visible if and only if there is no building with height greater than H_i between position x+0.5 and position i.

Constraints

  • 2\le N\le 2\times 10^5
  • 1\le C_x\le N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
C_1 C_2 \dots C_{N-1}

Output

Output the answer.

Sample Input 1

4
2 2 3

Sample Output 1

3

For example, (H_1,H_2,H_3,H_4)=(3,4,2,1) satisfies the condition. Indeed,

  • For x=1, the buildings visible from position x+0.5=1.5 are the first and second buildings; there are 2=C_1 such buildings.

  • For x=2, the buildings visible from position x+0.5=2.5 are the second and third buildings; there are 2=C_2 such buildings.

  • For x=3, the buildings visible from position x+0.5=3.5 are the second, third, and fourth buildings; there are 3=C_3 such buildings.

There are three sequences (H_1,H_2,H_3,H_4) satisfying the condition, including this one.

Sample Input 2

3
2 1

Sample Output 2

0

There may be no sequence (H_1,H_2,\dots, H_N) satisfying the condition.

Sample Input 3

7
3 3 3 3 4 4

Sample Output 3

85