题目描述

有一天，Snuke 收到了他朋友给他的长度为 $N$ 的排列 $a_1, a_2, ..., a_N$。

找出以下内容：

约束条件

• $1 ≦ N ≦ 200,000$
• $(a_1, a_2, ..., a_N)$ 是 $(1, 2, ..., N)$ 的一个排列。

输入

从标准输入读入数据，数据格式如下：

$N$ $a_1$ $a_2$ $...$ $a_N$

输出

打印答案。

请注意，答案可能不适合一个 32 位整数。

示例输入1

3
2 1 3

示例输出1

9

示例输入2

4
1 3 2 4

示例输出2

19

示例输入3

8
5 4 8 1 2 6 7 3

示例输出3

85