题目描述

给定一个长度为 $n$ 的序列 $[a_1,a_2,\dots,a_n]$ ,保证 $a$ 序列两两不同, 求所有区间最小值之和。即

输入格式

第一行一个整数 $n$

接下来 $n$ 个整数表示 $a$ 序列。

输出格式

一个整数，表示所有区间最小值之和。

3
2 1 3

9

4
1 2 3 4

20

8
5 4 8 1 2 6 7 3

85

数据规模与约定

$1 \leq n \leq 2 \times 10^5$，$1 \le a_i \leq 2 \times 10^5$, 保证 $a_i$ 两两不同。

$Subtask1$: $n \le 10^2$ , $20$ 分

$Subtask2$: $n \le 10^3$ , $20$ 分

$Subtask3$: $n \le 2 \times 10^4$ , $20$ 分

$Subtask4$: $n \le 2 \times 10^5$ , $40$ 分