思路

步骤一：第一棵树状数组，先把“两种情况的总和”都算出来

• 对每个位置 $i$，设

  • $cnt_i$ 表示从 $i$ 开始向右数，所有满足 $a_k < a_i$ 的元素个数，其中 $k > i$。

• 则以 $i$ 为左端点，右侧所有值 $<a_i$ 的二元组 $(j,k)$（$j<k$）总数为

题目内容

对于给定的由$n$个整数组成的数组{$a_1,a_2,...,a_n$}，计算其中有多少个三元组$(i,j,k)$满足$1≤i<j<k≦n$且$a_i>a_k>a_j$。例如，在数组{$4,1,2,3$}中三元组$(1,2,3),(1,2,4),(1,3,4)$都是满足条件的三元组。更具体地，计算:

$\sum_{1≤i＜j＜k≤n}[a_i＞a_k＞a_j]$

请编写一个函数，计算并返回满足条件的三元组的数量。

[名词解释] 本题公式中的中括号代表艾弗森括号，具体地，

$[P]=1$ 如果 $P$ 为真

$[P]=0$ 如果 $P$ 为假

输入描述

第一行输入一个整数$n(1≦n≦2×10^5)$代表数组中的元素个数。

第二行输入$n$个整数$a_1,a_2,...,a_n(-10^9≦a_i≦10^9)$代表数组中的元素。

输出描述

输出一个整数，表示满足条件的三元组个数。

样例1

输入

5
1 5 4 2 3

输出

2

说明

在这个样例中，满足条件的三元组有：

• $i=2、j=4$且$k=5$构成的三元组{$5,2,3$}
• $i=3、j=4$且$k=5$构成的三元组{$4,2,3$}

样例2

输入

20
-6 -9 -90 -73 89 -90 2 19 52 -16 -41 -22 85 24 -22 66 75 78 48 -36

输出

134