Increasing subsequence

Given a sequence of integers. Find the number of its increasing subsequences.

Input

The first line contains an integer $n(1\le n\le 500)$, representing the length of the sequence. The second line contains $n$ positive integers, each less than $5000$, which are the elements of the sequence.

Output

Print the number of increasing subsequences in the given sequence.

Examples