Increase

题目描述

今天，要比昨天做的更好。

Orange会给你一个序列 $a_i$。Orange喜欢这样的四元组 $(x,y,z,h)$，满足：

• $1 \le x < y < z < h \le n$
• $a_x \le a_y \le a_z \le a_h$

你的任务是，求出Orange喜欢的四元组的总数。

输入格式

输入一个整数 $n$，表示序列长度。 第二行为一个整数序列 $a_i$。

数据范围

$n \le 5000$ $a_i \le 10^9$

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

8
1 2 3 3 4 3 2 1

样例输出 #1

9