Counting Distinct Increasing Subsequences

You are given a sequence of integers (each integer's absolute value does not exceed 10⁹). Your task is to count the number of distinct increasing subsequences in the sequence. An increasing subsequence is defined as follows:

• It is a subsequence of the original sequence.
• Its length is at least 2.
• All its elements are in strictly increasing order.

If two increasing subsequences consist of the same numbers, they are counted as one. For example, for the sequence {1, 2, 3, 3}, there are 4 distinct increasing subsequences: {1,2}, {1,3}, {1,2,3}, {2,3}.

The problem can be mathematically represented as finding the number of distinct subsequences S such that:

[ \begin{aligned} & S \subseteq A,\ & |S| \ge 2,\ & \forall i,; S[i] < S[i+1]. \end{aligned} ]

inputFormat

The first line of the input contains a single integer n indicating the number of elements in the sequence. The second line contains n space-separated integers representing the sequence.

outputFormat

Output a single integer representing the count of distinct increasing subsequences.

sample

4
1 2 3 3

4