题目描述

Farmer John 的 $N$ 头奶牛的高度为 $1,2,…,N$。

一天，奶牛以某个顺序排成一行玩飞盘；令 $h_1,h_2,\dots h_N$ 表示此顺序下奶牛们的高度（因此 $h_1,h_2\dots h_N$ 是 $1,2\dots N$ 的一个排列）。

队伍中位于位置 $i$ 和 $j$ 的两头奶牛可以成功地来回扔飞盘当且仅当她们之间的每头奶牛的高度都低于 $min(h_i,h_j)$。

请计算所有可以成功地来回扔飞盘的奶牛所在位置对 $i$ 和 $j(i<j)$ 之间距离的总和。

位置 $i$ 和 $j$ 之间的距离为 $j-i+1$。

输入格式

输入的第一行包含一个整数 $N$。

第二行包含 $h_1,h_2,\dots h_N$，用空格分隔。

输出格式

输出所有可以成功地来回扔飞盘的奶牛所在位置对 $i$ 和 $j(i<j)$ 之间距离的总和。

注意这个问题涉及到的整数可能需要使用 $64$ 位整数型（例如，C 或 C++ 中的 “long long”）。

7
4 3 1 2 5 6 7

24

提示

$1≤N≤3×10^5$,
$h_1,h_2 \dots h_N$ 是 $1,2 \dots N$ 的一个排列。

样例解释

这个例子中可以成功的位置对如下：

(1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5), (5, 6), (6, 7)