Building 3

JOI Spring Training Camp 2014/15
Original Statement / Submission Site

Problem Statement

The International Olympiad in Informatics will be held in Japan. To welcome the contestants from around the world, it has been decided to decorate the high-rise buildings along the main road from the airport to the accommodation facility.

A famous designer was asked to create the design. The designer stated that the buildings used for the decoration must become taller as one proceeds from the airport toward the accommodation facility. In other words, if the heights of the decorated buildings, in order from nearest to the airport, are h1, h2, h3, ..., then they must satisfy

h1 < h2 < h3 < ....

To make the decoration as splendid as possible, JOI-kun wants to use as many buildings as possible.

There are N buildings along the main road from the airport to the accommodation facility. Building i is the i-th closest building to the airport. All N buildings have distinct heights.

JOI-kun realizes that an owner might make the unreasonable demand:

“My building must be used for the decoration, and among all decorated buildings, it must be the closest one to the accommodation facility.”

To prepare for every possible demand, JOI-kun calculates the following value for each building i:

Ai is the maximum possible number of decorated buildings, under the conditions that building i is used and that building i is the decorated building closest to the accommodation facility.

JOI-kun writes down the integer sequence A1, A2, ..., AN and submits it to Chairperson K of the Japanese Committee for the Olympiad in Informatics.

However, the note received by Chairperson K contains only an integer sequence B1, B2, ..., BN-1 of length N - 1. Since Chairperson K does not know the building heights, they cannot calculate the values Ai.

Chairperson K believes that JOI-kun must have forgotten to write exactly one number. Depending on the building heights, many different sequences A1, A2, ..., AN may be possible. Determine how many such possible sequences become B1, B2, ..., BN-1 after deleting exactly one element.

It is possible that JOI-kun made some other mistake, and therefore that no such sequence exists.

Task

Given an integer sequence B1, B2, ..., BN-1, determine the number of possible sequences A1, A2, ..., AN such that deleting exactly one element from A yields B.

Input

The input is given from standard input in the following format:

N
B1
B2
...
B(N-1)

• The first line contains the integer N, the number of buildings along the road from the airport to the accommodation facility.
• Each of the next N - 1 lines contains one integer Bj, the j-th value written in the note received by Chairperson K.

Output

Print one integer: the number of possible sequences A1, A2, ..., AN such that deleting exactly one element from the sequence yields B1, B2, ..., BN-1.

Constraints

• 2 ≤ N ≤ 1000000
• 1 ≤ Bj ≤ N for 1 ≤ j ≤ N - 1

Subtasks

Subtask 1 [10 points]

• N ≤ 8

Subtask 2 [30 points]

• N ≤ 300

Subtask 3 [60 points]

There are no additional constraints.

Sample Input 1

4
1
1
2

Sample Output 1

5

Explanation of Sample 1

There are four buildings along the main road from the airport to the accommodation facility. Let the height of building i be Hi.

Depending on the building heights, many different sequences A1, A2, A3, A4 are possible. Among them, the following five sequences become 1, 1, 2 after deleting exactly one element:

• 1, 2, 1, 2. For example, this occurs when H2 > H4 > H1 > H3. It also occurs when H2 > H1 > H4 > H3.
• 1, 1, 2, 3. For example, this occurs when H4 > H3 > H1 > H2.
• 1, 1, 2, 1. For example, this occurs when H3 > H1 > H2 > H4.
• 1, 1, 2, 2. For example, this occurs when H3 > H4 > H1 > H2.
• 1, 1, 1, 2. For example, this occurs when H4 > H1 > H2 > H3.

Sample Input 2

8
1
1
2
1
2
3
1

Sample Output 2

15