問題文

すぬけ君はある日友人から長さ $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$

出力

$1$ 行に答えを出力する。

なお、32bit整数型に答えが収まるとは限らないことに注意すること。

入力例 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