该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给你一个长 $n$ 的正整数排列 $p$，你需要统计有多少个四元组 $[a,b,c,d]$ 满足如下条件：

1. $a<b<c<d$
2. $p_a<p_c$
3. $p_b>p_d$

长为 $n$ 的排列：$1\sim n$ 各出现一次的数列。

输入格式

第一行一个正整数 $n$, 表示序列长度。

第二行 $n$ 个数，代表对应排列。

输出格式

一行一个整数，表示四元组数量。

样例

Input # 1

6
5 3 6 1 4 2

Output # 1

3

Input # 2

10
5 1 6 2 8 3 4 10 9 7

Output # 2

28

数据范围与提示

对于 $20\%$ 数据，有 $n\le 50$

对于 $40\%$ 数据，有 $n\le 500$

对于 $60\%$ 数据，有 $n\le 2000$

对于 $100\%$ 数据，有 $n\le 8000$