← 返回题目列表

AtCoder · arc104_f

F. 可见性序列

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

有 N 在建建筑物排成一排,编号 1, 2, \ldots, N 从左到右。

给定的是一个整数序列 X 长度 N.建筑物的高度 i, H_i,可以是之间的整数之一 1 和 X_i (含)。

对于每个 i 这样 1 \leq i \leq N,让我们定义 P_i 如下:

  • 如果有一个整数 j (1 \leq j < i) 这样 H_j > H_i, P_i 是这样的最大值 j。否则, P_i is -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,如下:

  • H = (1, 1, 1),其中 P is (-1, -1, -1);
  • H = (1, 2, 1),其中 P is (-1, -1, 2);
  • H = (2, 1, 1),其中 P is (-1, 1, 1);
  • H = (2, 2, 1),其中 P is (-1, -1, 2);
  • H = (3, 1, 1),其中 P is (-1, 1, 1);
  • H = (3, 2, 1),其中 P is (-1, 1, 2).

因此,有四个整数序列 P 可以是: (-1, -1, -1), (-1, -1, 2), (-1, 1, 1),和 (-1, 1, 2).


示例输入 2

3
1 1 2

示例输出 2

1

我们有两名候选人 H,如下:

  • H = (1, 1, 1),其中 P is (-1, -1, -1);
  • H = (1, 1, 2),其中 P is (-1, -1, -1).

因此,有一个整数序列 P 可以。


示例输入 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