题目描述

给定正整数 $n$ 及 $1$ 到 $n$ 的一个排列 $a_1,a_2,\cdots,a_n$，请统计其中有多少由三个数字组成的三元组，满足 132 型。所谓 132 型，是指三个下标 $(i,j,k)$，满足 $i<j<k$ 且 $a_i<a_k<a_j$。即，中间的数字最大，尾部的数字第二大，头部的数字最小。

输入格式

• 第一行：单个整数 $n$；
• 第二行：$n$ 个整数 $a_1,a_2,\cdots, a_n$。

输出格式

• 单个整数：表示符合条件的三元组数量。注意这个数字可能超过 $2^{32}$。

5
1 3 2 5 4

4

样例解释 1

（1，3，2），（1，5，4），（3，5，4），（2，5，4）共四组

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 300$；
• 对于 $60\%$ 的数据，$1\leq n\leq 5000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 20000$。