题目描述

给你 $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 4 4 5 3

5

样例解释

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

7
81 35 47 3 26 51 81

11

样例解释

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

数据规模

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