Count Increasing Subsequences of Length 3

You are given a sequence of n integers. Your task is to count the number of increasing subsequences of length 3 within this sequence. In other words, you need to find the number of triplets (i, j, k) with i < j < k such that:

\(a_i < a_j < a_k\)

Input: The first line contains a single integer n. The second line contains n space-separated integers representing the sequence.

Output: Output a single integer, the number of increasing subsequences of length 3.

Note: If there is no valid subsequence, output 0.

inputFormat

The first line contains an integer \(n\) (the number of elements in the sequence). The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\).

outputFormat

Output a single integer representing the total number of increasing subsequences of length 3 found in the sequence.

9
1 2 3 4 5 6 7 8 9

84