题目描述

Farmer John 的 $N$ 头奶牛排成一行，高度恰好是 $1$ 到 $N$ 的一个排列。令 $h_1, h_2, \ldots, h_N$ 表示从左到右每头奶牛的高度。

队伍中位于位置 $i$ 和 $j$（$i \lt j$）的两头奶牛可以互相传递飞盘，当且仅当她们之间的每一头奶牛的高度都严格小于 $\min(h_i, h_j)$。

请求出所有可以互相传递飞盘的位置对 $(i, j)$ 之间的距离总和，其中位置 $i$ 和 $j$ 之间的距离定义为 $j - i + 1$。

输入格式

第一行包含一个整数 $N$（$1 \le N \le 3 \times 10^5$）。

第二行包含 $N$ 个整数 $h_1, h_2, \ldots, h_N$，用空格分隔，表示奶牛的高度排列。

输出格式

输出一个整数，表示所有可以互相传递飞盘的位置对的距离总和。请注意答案可能超出 32 位整数范围，请使用 64 位整数存储。

样例

7
4 3 1 2 5 6 7

24

提示

可以互相传递飞盘的位置对为：$(1,2), (1,5), (2,3), (2,4), (2,5), (3,4), (4,5), (5,6), (6,7)$。

距离分别为 $2, 5, 2, 3, 4, 2, 2, 2, 2$，总和为 $24$。

数据范围

• 测试点 1 满足 $N = 7$，为官方样例。
• 测试点 2-3 满足 $N \le 20$。
• 测试点 4-6 满足 $N \le 5000$。
• 测试点 7-10 满足 $N \le 3 \times 10^5$。