Permutation Reconstruction

There are \( n \) people standing in a line. Each person holds a unique number such that the \( n \) numbers form a permutation of \( \{1,2,\dots,n\} \). Each person reports a number from one of his neighbors with the following rules:

• Person 1 has only a right neighbor, so he always reports the number held by Person 2.
• Person \( n \) has only a left neighbor, so he always reports the number held by Person \( n-1 \).
• Any person \( i \) for \( 2 \le i \le n-1 \) may report either the number on his left (Person \( i-1 \)) or on his right (Person \( i+1 \)).

You are given the sequence of reported numbers \( r_1, r_2, \dots, r_n \) (in order from Person 1 to Person \( n \)). Determine the number of possible original permutations \( A_1,A_2,\dots,A_n \) that can yield these reports, where the following conditions must be met:

• \( A_2 = r_1 \) (since Person 1 reports Person 2's number).
• \( A_{n-1} = r_n \) (since Person \( n \) reports Person \( n-1 \)'s number).
• For each \( i \) with \( 2 \le i \le n-1 \), it must hold that \( r_i = A_{i-1} \) or \( r_i = A_{i+1} \).

Note that the reported number for persons \( 2 \le i \le n-1 \) can come from either neighbor, so the original permutation is not uniquely determined. Your task is to calculate the total number of valid permutations satisfying these conditions.

inputFormat

The input consists of two lines:

• The first line contains a single integer \( n \) (the number of people).
• The second line contains \( n \) integers \( r_1, r_2, \dots, r_n \) separated by spaces, representing the reported numbers.

outputFormat

Output a single integer: the number of possible original permutations that are consistent with the reported numbers.

sample

3
2 1 2

2