P1637 Triple Increasing Subsequence

Erwin has recently become very interested in something called `thair`... In a sequence with $n$ integers $a_1,a_2,\ldots,a_n$, three numbers are called `thair` if and only if $i

The first line contains a positive integer $n$. The second line contains $n$ integers $a_1,a_2,\ldots,a_n$.

Print one integer in a single line indicating the number of `thair`.

#### Sample 2 Explanation The $7$ `thair` are: - 1 2 3. - 1 2 4. - 1 2 3. - 1 2 4. - 1 3 4. - 2 3 4. - 2 3 4. #### Constraints - For $30\%$ of the testdata, it is guaranteed that $n\le100$. - For $60\%$ of the testdata, it is guaranteed that $n\le2000$. - For $100\%$ of the testdata, it is guaranteed that $1 \leq n\le3\times10^4$ and $1\le a_i\leq 10^5$. Translated by ChatGPT 5