Adjacent Maximums - Repovive Starter Round 7 | Repovive

21B. Adjacent Maximums

1000 pts1s256 MB

You are given a permutation $b$ of the integers from $2$ to $n$ .

A permutation $p$ of the integers from $1$ to $n$ is called good if, for every $1 \le i < n$ ,

b_i = \max(p_i,p_{i+1}).

Find the number of good permutations.

Constraints

$2 \le n \le 1000$
$b$ is a permutation of the integers from $2$ to $n$

Input

The input consists of two lines:

n

b_1 \quad b_2 \quad \cdots \quad b_{n-1}

Output

Output one integer: the number of good permutations.

Samples

Input

6
6 4 2 3 5

Explanation

The two good permutations are $[6,4,1,2,3,5]$ and $[6,4,2,1,3,5]$ . For each of them, the maximums of adjacent pairs are $[6,4,2,3,5]$ .

Output

Input

5
2 5 3 4

Explanation

The first required maximum forces the first two elements of $p$ to be $1$ and $2$ in some order. The second required maximum then forces the third element to be $5$ , making the next adjacent maximum at least $5$ instead of $3$ . Therefore, no good permutation exists.

Output

You are given a permutation $b$ of the integers from $2$ to $n$ .

A permutation $p$ of the integers from $1$ to $n$ is called good if, for every $1 \le i < n$ ,

b_i = \max(p_i,p_{i+1}).

Find the number of good permutations.

$2 \le n \le 1000$
$b$ is a permutation of the integers from $2$ to $n$

The input consists of two lines:

n

b_1 \quad b_2 \quad \cdots \quad b_{n-1}

The two good permutations are $[6,4,1,2,3,5]$ and $[6,4,2,1,3,5]$ . For each of them, the maximums of adjacent pairs are $[6,4,2,3,5]$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

21B. Adjacent Maximums

Constraints

Input

Output

Samples

21B. Adjacent Maximums

Constraints

Input

Output

Samples