Given a permutation of n elements (1, 2, ..., n): A = (a₁, a₂, ..., a_n). We define a sequence P(A)=(p₁, p₂, …, p_n-1) where p_i = 0 if a_i > a_i+1 and p_i = 1 if a_i < a_i+1. Given a permutation B, find the number of all permutations C where P(C)=P(B) including the permutation B itself.

The length of your solution should not be more than 0.5kB.

Input

Multiple test cases. For each test case:

The first line contains an integer n(1<= n <=100).The second line contains n integers representing the permutation, all of which are separated by single spaces.

Input terminates by a single zero.

Output

For each test case:

The output contains a single line with a single integer - the number of the permutations having the same value for P(A) when given the permutation A.

Example

Input:
2
1 2
4
1 3 2 4
0

Output:
1
5