B - Door Selection Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君は、N 個の部屋が一列に並んだ建物を通り抜けようとしています。

建物の入口は部屋 1 に繋がっており、部屋 1, 2, \ldots, N をこの順に通り抜けると出口に到達します。各部屋 i（1 \leq i \leq N）には A_i 個のドアがあり、1 から A_i までの番号が付いています。どのドアを選んでも次の部屋（部屋 N の場合は出口）に進むことができます。

高橋君は各部屋でちょうど 1 つのドアを選んで通ります。各部屋で選んだドアの番号をこの順に並べた列によって経路を表すとき、入口から出口までの経路は全部で何通りありますか。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^{18}
  • A_1 \times A_2 \times \cdots \times A_N \leq 10^{18}
  • 入力はすべて整数

入力

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

N
A_1
A_2
\vdots
A_N

1 行目に部屋の数 N が、続く N 行のうち i 行目に部屋 i のドアの数 A_i が与えられます。

出力

入口から出口までの経路の総数を整数として 1 行で出力してください。

入力例 1

3
2
3
2

出力例 1

12

入力例 2

4
1
2
1
3

出力例 2

6

入力例 3

8
4
1
3
2
5
1
2
3

出力例 3

720

入力例 4

20
2
2
2
2
2
2
2
2
2
2
3
3
5
5
1
1
2
3
4
1

出力例 4

5529600

入力例 5

1
1000000000000000000

出力例 5

1000000000000000000

Score : 233 pts

Problem Statement

Takahashi is trying to pass through a building consisting of N rooms arranged in a row.

The entrance of the building is connected to room 1, and by passing through rooms 1, 2, \ldots, N in this order, he reaches the exit. Each room i (1 \leq i \leq N) has A_i doors, numbered from 1 to A_i. Choosing any door allows him to proceed to the next room (or to the exit in the case of room N).

Takahashi chooses exactly one door to pass through in each room. A path is represented by the sequence of door numbers chosen in each room, listed in order. How many distinct paths are there from the entrance to the exit?

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^{18}
  • A_1 \times A_2 \times \cdots \times A_N \leq 10^{18}
  • All input values are integers.

Input

The input is given in the following format.

N
A_1
A_2
\vdots
A_N

The first line contains the number of rooms N, and the i-th of the following N lines contains the number of doors A_i in room i.

Output

Output the total number of paths from the entrance to the exit as an integer on a single line.

Sample Input 1

3
2
3
2

Sample Output 1

12

Sample Input 2

4
1
2
1
3

Sample Output 2

6

Sample Input 3

8
4
1
3
2
5
1
2
3

Sample Output 3

720

Sample Input 4

20
2
2
2
2
2
2
2
2
2
2
3
3
5
5
1
1
2
3
4
1

Sample Output 4

5529600

Sample Input 5

1
1000000000000000000

Sample Output 5

1000000000000000000