### Problem Statement

A subsequence of a sequence of numbers a is the result of erasing zero or more elements from a. An increasing subsequence is a subsequence in which each element (except the first) is strictly greater than the previous element. An increasing subsequence of a is maximal if unerasing any of the erased elements of a does not result in a longer increasing subsequence.

For example, if a={1,3,2,6,4,5} then {1,3,4} is an increasing subsequence but not a maximal increasing subsequence. {1,2,4,5}, {1,3,4,5}, {1,2,6} and {1,3,6}, on the other hand, are maximal increasing subsequences.

You will be given a as a int[] representing a sequence of distinct numbers. Return the number of maximal increasing subsequences it contains.

### Definition

 Class: IncreasingSubsequences Method: count Parameters: int[] Returns: long Method signature: long count(int[] a) (be sure your method is public)

### Constraints

-a will contain between 1 and 50 elements, inclusive.
-Each element of a will be between 1 and 1000000000 (109), inclusive.
-All elements of a will be distinct.

### Examples

0)

 `{1,3,2,6,4,5}`
`Returns: 4`
 The example from the problem statement.
1)

 `{1000000000,100000000,10000000,1000000,100000,10000,1000,100,10,1}`
`Returns: 10`
 All maximal increasing subsequences have length 1.
2)

 `{1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000}`
`Returns: 1`
 Since the whole sequence is an increasing subsequence, there cannot be any other maximal increasing subsequence.
3)

 `{564,234,34,4365,424,2234,306,21,934,592,195,2395,2396,29345,13295423,23945,2}`
`Returns: 41`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7753

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10672&pm=7753

soul-net

#### Testers:

PabloGilberto , brett1479 , Cosmin.ro , Olexiy

#### Problem categories:

Dynamic Programming