B - ARC Wrecker 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点: 400 点

問題文

AtCoder 街道には N 個のビルが建設されています。最初、左から i 番目のビルは A_i 階建てです。

ARC 解体業者の社長である高橋君は、以下の操作を好きな回数だけ行うことができます。1 回も操作を行わないことも可能です。

  • 好きな正の整数 X を選び、X 階の高さから大砲を発射する。そのとき、現時点で X 階建て以上であるすべてのビルについて、階数が 1 減少する。

あり得る最終的なビルの景観の数を 10^{9} + 7 で割った余りを求めてください。

ただし、景観 A と景観 B が異なるとは、以下のことを指します。

  • 景観 A における、左から i 番目のビルの高さを P_i とする。
  • 景観 B における、左から i 番目のビルの高さを Q_i とする。
  • P_i \neq Q_i となる i が 1 つでも存在する場合、景観 A と景観 B は異なる。

制約

  • 1 \leq N \leq 100000
  • 1 \leq A_i \leq 10^{9}
  • 入力はすべて整数

入力

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

N
A_1 A_2 \cdots A_N

出力

答えを出力してください。

入力例 1

2
1 2

出力例 1

4

操作後のビルの高さとしてあり得るものは、以下の 4 通りです。

  • (ビル 1 の階数, ビル 2 の階数) = (0, 0)
  • (ビル 1 の階数, ビル 2 の階数) = (0, 1)
  • (ビル 1 の階数, ビル 2 の階数) = (1, 1)
  • (ビル 1 の階数, ビル 2 の階数) = (1, 2)

入力例 2

6
5 3 4 1 5 2

出力例 2

32

入力例 3

7
314 159 265 358 979 323 846

出力例 3

492018656

全部で 20192492160000 通りの景観があり得ますが、それを 10^{9} + 7 で割った余りである 492018656 を出力すると正解になります。

Score : 400 points

Problem Statement

There are N buildings along AtCoder road. Initially, the i-th building from the left has A_i stories.

Takahashi, the president of ARC Wrecker, Inc., can do the following operation any number of times, possibly zero:

  • Choose a positive integer X that he likes and shoot a cannonball at that height, which decreases by 1 the number of stories in each building with X or more stories.

Find the number of possible final sceneries of buildings, modulo (10^{9} + 7).

We consider two sceneries A and B different when the following holds:

  • let P_i be the number of stories of the i-th building from the left in scenery A;
  • let Q_i be the number of stories of the i-th building from the left in scenery B;
  • we consider sceneries A and B different when P_i \neq Q_i for one or more indices i.

Constraints

  • 1 \leq N \leq 100000
  • 1 \leq A_i \leq 10^{9}
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

2
1 2

Sample Output 1

4

There are four possible combinations of heights of the buildings, as follows:

  • (Building 1, Building 2) = (0, 0)
  • (Building 1, Building 2) = (0, 1)
  • (Building 1, Building 2) = (1, 1)
  • (Building 1, Building 2) = (1, 2)

Sample Input 2

6
5 3 4 1 5 2

Sample Output 2

32

Sample Input 3

7
314 159 265 358 979 323 846

Sample Output 3

492018656

There are 20192492160000 possible final sceneries. The correct output is that number modulo 10^{9} + 7, which is 492018656.