题目描述

信息学课下课啦！小明和他的同桌小华商量今天轮到谁请喝汽水。两个人你一言我一语，谁也不承认是轮到自己请。突然，小华想出来一个游戏，对小明说：“如果你赢了，今天就是我请。”小明听到有免费喝汽水的机会，答应了。

游戏开始时，给出一个仅包含非负整数的数组 $a$ ，小明可以从中抽取 $3$ 个不同位置的数( $a_i$ , $a_j$ , $a_k$ 且 $i \lt j \lt k$ )组成一个三个数的序列，问有多少种选择的方案使选出来的三个数是上升序列 ( 即 $a_i \lt a_j \lt a_k$ )。小明觉得很简单，所以交给你来解决啦！

输入格式

第一行输入一个正整数 $n$ ，表示数组 $a$ 中元素个数；

第二行 $n$ 个非负整数，表示 $a$ 数组中的第 $i$ 个元素 $a_i$ 。

数据范围

对于 60% 的数据，$1 \le n \le 100$ ；

对于 100% 的数据，$1 \le n \le 3000$ ，$0 \le a_i \le 100$ 。

输出格式

一个数，表示满足题意的方案数。

样例

5
1 3 4 2 5

5

8
1 3 5 2 4 6 7 8

40

样例解释

样例 1 中，5 种方案分别为：{1 3 4}，{1 3 5}，{1 4 5}，{1 2 5}，{3 4 5}。