The International Olympiad in Informatics is being held in Japan. To welcome the athletes from around the world, it has been decided to decorate the skyscrapers along the main street from the airport to the accommodation facility. A famous designer was commissioned for the design, and they stated that the buildings used for decoration must increase in height from the airport toward the accommodation facility. In other words, if we denote the heights of the buildings used for decoration in order from the one closest to the airport as $h_1, h_2, h_3, \dots$, then it must be that $h_1 < h_2 < h_3 < \dots$.

To make the decorations as spectacular as possible, we want to use as many buildings as possible. JOI, who was tasked with selecting the buildings to be decorated, realized that there is a possibility that a building owner might make the unreasonable request: "I want you to definitely use my building for decoration. Furthermore, to make the building stand out, I want you to choose the buildings such that my building is the one closest to the accommodation facility among all the buildings used for decoration."

There are $N$ buildings along the main street from the airport to the accommodation facility, and we call the $i$-th building from the airport ($1 \le i \le N$) building $i$. The heights of the $N$ buildings are all distinct. JOI has pre-calculated the following: "When choosing buildings such that building $i$ is used for decoration and building $i$ is the one closest to the accommodation facility among all buildings used for decoration, the maximum number of buildings that can be chosen is $A_i$."

JOI noted down the integer sequence $A_1, A_2, \dots, A_N$ calculated in this way and submitted it to Chairman K of the Japanese Committee for the International Olympiad in Informatics.

However, the note that Chairman K received actually only contained an integer sequence $B_1, B_2, \dots, B_{N-1}$ of length $N-1$. Since Chairman K does not know the information about the heights of the buildings, he cannot calculate the values of $A_i$.

Chairman K thought that JOI must have forgotten to write down one number. Various sequences $A_1, A_2, \dots, A_N$ can be considered depending on the heights of the buildings. Among these, how many sequences are there such that removing one value from the sequence results in the sequence $B_1, B_2, \dots, B_{N-1}$?

Note that in reality, JOI might have made other mistakes in writing. Depending on the values of $B_1, B_2, \dots, B_{N-1}$, there might be no such sequence at all.

Task

Given an integer sequence $B_1, B_2, \dots, B_{N-1}$ of length $N-1$, write a program to determine how many sequences $A_1, A_2, \dots, A_N$ can be considered such that removing one value from the sequence results in the sequence $B_1, B_2, \dots, B_{N-1}$.

Input

Read the following from standard input:

• The first line contains an integer $N$. This represents that there are $N$ buildings along the main street from the airport to the accommodation facility.
• The $j$-th line ($1 \le j \le N-1$) of the following $N-1$ lines contains an integer $B_j$. This is the $j$-th value of the integer sequence written in the note received by Chairman K.

Output

Output the integer representing the number of sequences $A_1, A_2, \dots, A_N$ such that removing one value from the sequence results in the sequence $B_1, B_2, \dots, B_{N-1}$ in a single line.

Constraints

All input data satisfies the following conditions:

• $2 \le N \le 1\,000\,000$.
• $1 \le B_j \le N$ ($1 \le j \le N-1$).

Subtasks

1. (10 points) $N \le 8$ is satisfied.
2. (30 points) $N \le 300$ is satisfied.
3. (60 points) No additional constraints.

Examples

Input 1

4
1
1
2

Output 1

5

There are 4 buildings along the main street from the airport to the accommodation facility. Let $H_i$ be the height of building $i$. Various sequences $A_1, A_2, A_3, A_4$ can be considered depending on the heights of the buildings. Among these, there are 5 ways such that removing one value from the sequence results in the sequence $1, 1, 2$:

• Sequence $1, 2, 1, 2$. For example, when $H_2 > H_4 > H_1 > H_3$, we have $A_1 = 1, A_2 = 2, A_3 = 1, A_4 = 2$. Also, when $H_2 > H_1 > H_4 > H_3$, we have $A_1 = 1, A_2 = 2, A_3 = 1, A_4 = 2$.
• Sequence $1, 1, 2, 3$. For example, when $H_4 > H_3 > H_1 > H_2$, we have $A_1 = 1, A_2 = 1, A_3 = 2, A_4 = 3$.
• Sequence $1, 1, 2, 1$. For example, when $H_3 > H_1 > H_2 > H_4$, we have $A_1 = 1, A_2 = 1, A_3 = 2, A_4 = 1$.
• Sequence $1, 1, 2, 2$. For example, when $H_3 > H_4 > H_1 > H_2$, we have $A_1 = 1, A_2 = 1, A_3 = 2, A_4 = 2$.
• Sequence $1, 1, 1, 2$. For example, when $H_4 > H_1 > H_2 > H_3$, we have $A_1 = 1, A_2 = 1, A_3 = 1, A_4 = 2$.

Input 2

8
1
1
2
1
2
3
1

Output 2

15