Building 3

The International Olympiad in Informatics will be held in Japan. To welcome the contestants, the city plans to decorate the tall buildings along the main avenue from the airport to the hotel where the athletes stay. A well-known designer said the buildings used for decoration must get taller as you move from the airport toward the hotel. In other words, if the heights of the decorated buildings are $h_1, h_2, h_3, \cdots$ in order from the one closest to the airport, then $h_1 < h_2 < h_3 < \cdots$ must hold.

To make the decoration as impressive as possible, the number of decorated buildings should be as large as possible. JOI was asked to choose the buildings. He realized that a building owner might demand two things at once: that the owner's building must be used for decoration, and that it must be the one closest to the hotel among the decorated buildings, so that it stands out.

There are $N$ buildings along the avenue. Call the building that is $i$-th closest to the airport building $i$ ($1 \le i \le N$). All $N$ heights are different. To be ready for any such demand, JOI computed the following in advance. Suppose building $i$ is used for decoration and is the closest to the hotel among the decorated buildings. Then the maximum number of buildings that can be chosen is $A_i$. JOI wrote the integer sequence $A_1, A_2, \ldots, A_N$ and submitted it to Chairman K of the JOI committee.

However, the note Chairman K received contained only the integer sequence $B_1, B_2, \ldots, B_{N-1}$ of length $N-1$. Chairman K does not know the building heights, so Chairman K cannot compute the values $A_i$.

Chairman K thinks JOI forgot one number. Among all possible integer sequences $A_1, A_2, \ldots, A_N$, how many become $B_1, B_2, \ldots, B_{N-1}$ after deleting exactly one entry?

JOI may have made other mistakes as well. For some values of $B$, there may be no such sequence at all.

Write a program that counts the possible sequences $A_1, \ldots, A_N$ that become $B_1, \ldots, B_{N-1}$ after removing one entry.

The first line contains $N$, the number of buildings along the avenue. Each of the next $N-1$ lines contains $B_j$ ($1 \le j \le N-1$), the $j$-th value in the note.

Print one integer on a single line: the number of possible sequences $A_1, \ldots, A_N$ that become $B_1, \ldots, B_{N-1}$ after removing one entry.

$2 \le N \le 1\,000\,000$.

$1 \le B_j \le N$ for $1 \le j \le N-1$.