派蒙计数

题目描述

派蒙 有一个 $n$ 长序列 $A = a_1,...,a_n$，他想知道同时满足以下条件的四元 $(i,j,k,l)$ 的数量：

• $1 \leq i \lt j \lt k \lt l \leq n$
• $a_i \leq a_j \leq a_k \leq a_l$。

输入格式

第一行一个正整数 $n$，

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

输出格式

一个整数表示答案。

8
1 2 3 3 4 3 2 1

9

6
1 1 1 2 2 3

15

提示

【数据范围】

对于所有数据：$1 \leq n \leq 5 \times 10^3，1 \leq a_i \leq 10^{9}$。