题目描述

给你 $n$ 个数字 $a_1,a_2,…,a_n$，这些数字各不相同。询问共有多少对数字 $(i,j) (1≤i<j≤n)$，$a_i$ 到 $a_j$ 中没有数字比 $a_i$ 或 $a_j$ 大。 即对所有位置$k(i<k<j)$， 有 $a_k<min(a_i,a_j)$。

输入格式

第一行一个整数 $n$。

接下来一行共 $n$ 个数。

输出格式

输出1个数，表示答案。

5
2 5 4 6 3

5

样例解释

符合要求的数对有 $(1,2),(2,3),(2,4),(3,4),(4,5)$。

数据规模

对于100%的数据，保证$1≤n≤2×10^5,1≤a_i≤10^9$。