题目描述

给你一个长度为 $n$ 的整数序列 $a_1,a_2,...,a_n$，请求出有多少个三元组 $(i,j,k)$，满足 $1\le i\lt j \lt k\le n$ 且 $a_i\lt a_j\gt a_k$。

输入格式

• 第一行一个整数 $n$。
• 第二行 $n$ 个整数 $a_1,a_2,...,a_n$。

输出格式

• 一行一个整数，表示答案。

输入输出样例 #1

输入 #1

7
3 2 9 9 3 4 2

输出 #1

16

说明/提示

• 对于测试点 $1\sim 8$：$1\le n\le 300$。
• 对于测试点 $9\sim 12$：$1\le n\le 3000$。
• 对于测试点 $13\sim 20$：$1\le n\le 2\times 10^5$。

对于全部测试点，有 $1\le a_i\le 100$。