PERMUT3 - Another Permutation Problem

Given a permutation of n elements (1, 2, ..., n): A = (a1, a2, ..., an). We define a sequence P(A)=(p1, p2, …, pn-1) where pi = 0 if ai > ai+1 and pi = 1 if ai < ai+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

Added by:Fudan University Problem Setters
Date:2008-03-21
Time limit:1s
Source limit:512B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM Southeastern European Regional Contest 2001

hide comments
2018-12-27 19:23:18
Answer can be out of range of 64 bit int.
2015-01-15 09:42:11 (Tjandra Satria Gunawan)(曾毅昆)
512B source limit really make this problem more interesting!
Got AC in 0.00s with 502B code length, really close to the limit ;-)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.