问题 4819 --4.三元组数

4819: 4.三元组数

题目描述

  小 Z 给了你一个数列$\{a_n\}$ ,其中的元素两两不同。
小 Z 要数的是对于$i,j,k(i<j<k)$  满足 $a_i<a_k$ 且 $a_k<a_j$ 的三元组 $(i,j,k)$ 的个数。由于数列太长了,现在小 Z 想请你帮他计算。

输入

第一行有一个正整数$n$ ,即数列长度。
接下来一行有 $n$ 个不同的正整数,第 $i$ 个数表示 $a_i$

输出

一个整数,即满足要求的三元组个数。

样例输入输出

输入#1 复制
3
1 3 2
输出#1 复制
1

提示

对于 $20\%$  的数据, $1\leq n \leq 100$ ;
对于 $40\%$  的数据, $1\leq n \leq 1000$ ;
对于 $60\%$  的数据, $1\leq n \leq 100000$ ;
对于 $100\%$  的数据, $1\leq n \leq 200000,   1\leq a_i \leq n$。

序号 标题 作者 发表时间 费用 订购数 操作