F - Visibility Sequence Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

一列に並んだ N 棟のビルが建設中であり、ビルには左から順番に 1, 2, \ldots, N の番号がついています。

長さ N の整数列 X が与えられ、ビル i の高さ H_i は、1 以上 X_i 以下の整数のいずれかにすることができます。

1 \leq i \leq N に対して、P_i を次のように定めます。

  • H_j > H_i を満たすような整数 j (1 \leq j < i) が存在する場合はそのような j の最大値、存在しない場合は -1 とする

全てのビルの高さの組み合わせを考えるとき、 P としてありうる整数列の個数を 1000000007 で割った余りを求めてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq X_i \leq 10^5
  • 入力は全て整数である

入力

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

N
X_1 X_2 \cdots X_N

出力

全てのビルの高さの組み合わせを考えるとき、 P としてありうる整数列の個数を 1000000007 で割った余りを出力せよ。

入力例 1

3
3 2 1

出力例 1

4

H としては、次の 6 通りが考えられます。

  • H = (1, 1, 1) のとき、P は (-1, -1, -1) である
  • H = (1, 2, 1) のとき、P は (-1, -1, 2) である
  • H = (2, 1, 1) のとき、P は (-1, 1, 1) である
  • H = (2, 2, 1) のとき、P は (-1, -1, 2) である
  • H = (3, 1, 1) のとき、P は (-1, 1, 1) である
  • H = (3, 2, 1) のとき、P は (-1, 1, 2) である

よって、P としてありうる整数列は (-1, -1, -1), (-1, -1, 2), (-1, 1, 1), (-1, 1, 2) の 4 個です。

入力例 2

3
1 1 2

出力例 2

1

H としては、次の 2 通りが考えられます。

  • H = (1, 1, 1) のとき、P は (-1, -1, -1) である
  • H = (1, 1, 2) のとき、P は (-1, -1, -1) である

よって、P としてありうる整数列は 1 個です。

入力例 3

5
2 2 2 2 2

出力例 3

16

入力例 4

13
3 1 4 1 5 9 2 6 5 3 5 8 9

出力例 4

31155

Score : 1000 points

Problem Statement

There are N buildings under construction arranged in a row, numbered 1, 2, \ldots, N from left to right.

Given is an integer sequence X of length N. The height of Building i, H_i, can be one of the integers between 1 and X_i (inclusive).

For each i such that 1 \leq i \leq N, let us define P_i as follows:

  • If there is an integer j (1 \leq j < i) such that H_j > H_i, P_i is the maximum such j. Otherwise, P_i is -1.

Considering all possible combinations of the buildings' heights, find the number of integer sequences that P can be, modulo 1000000007.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq X_i \leq 10^5
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
X_1 X_2 \cdots X_N

Output

Print the number of integer sequences that P can be when all possible combinations of the buildings' heights are considered, modulo 1000000007.

Sample Input 1

3
3 2 1

Sample Output 1

4

We have six candidates for H, as follows:

  • H = (1, 1, 1), for which P is (-1, -1, -1);
  • H = (1, 2, 1), for which P is (-1, -1, 2);
  • H = (2, 1, 1), for which P is (-1, 1, 1);
  • H = (2, 2, 1), for which P is (-1, -1, 2);
  • H = (3, 1, 1), for which P is (-1, 1, 1);
  • H = (3, 2, 1), for which P is (-1, 1, 2).

Thus, there are four integer sequences that P can be: (-1, -1, -1), (-1, -1, 2), (-1, 1, 1), and (-1, 1, 2).

Sample Input 2

3
1 1 2

Sample Output 2

1

We have two candidates for H, as follows:

  • H = (1, 1, 1), for which P is (-1, -1, -1);
  • H = (1, 1, 2), for which P is (-1, -1, -1).

Thus, there is one integer sequence that P can be.

Sample Input 3

5
2 2 2 2 2

Sample Output 3

16

Sample Input 4

13
3 1 4 1 5 9 2 6 5 3 5 8 9

Sample Output 4

31155