B - Minimum Sum Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400 点

問題文

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

Score : 400 points

Problem Statement

One day, Snuke was given a permutation of length N, a_1, a_2, ..., a_N, from his friend.

Find the following:

Constraints

  • 1 ≦ N ≦ 200,000
  • (a_1, a_2, ..., a_N) is a permutation of (1, 2, ..., N).

Input

The input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

Print the answer.

Note that the answer may not fit into a 32-bit integer.

Sample Input 1

3
2 1 3

Sample Output 1

9

Sample Input 2

4
1 3 2 4

Sample Output 2

19

Sample Input 3

8
5 4 8 1 2 6 7 3

Sample Output 3

85