题目描述

给一个打乱的 $1∼n$ 的排列 $a_i(1 \le i \le n)$ ，要求计数形如 $(i,j,p,q)$ 的位置四元组数量。

其中要求：

$①1 \le i < j < p < q \le n$

$②a_i<a_p<a_j<a_q。$

一个简单的例子：例如 n=4 时，排列 {1,3,2,4} 具备一个这样的位置四元组

输入格式

第一行一个正整数 n ，表示排列的长度。

接下来一行 n 个正整数，表示这个打乱的排列。其中保证 $1∼n$ 各出现一次。

输出格式

一行一个整数表示有几个这样的四元组。

输入输出样例 #1

输入 #1

5
1 3 2 4 5

输出 #1

2

说明/提示

对于100%的数据，保证 $1 \le n \le 5000$