cards

Problem Description

Rar the Cat has N cards, with unique labels 1 through N. He arranges them in some order in a row, where the ith card from the left is A_i.

Peanut comes in, and picks a random non-empty consecutive segment of cards. For each segment Peanut could pick, there exists a card with the minimum value. Find the sum of the minimum values among all possible segments Peanut could choose. Refer to the sample for more details.

Input

The first line of input will contain one integer, N.

The next line of input will contain N integers, with the ith integer containing A_i.

Output

The output should contain one integer, the sum of the minimum values among all possible segments.

Limits

Subtask 1 (16%): 1 ≤ N ≤ 300.

Subtask 2 (30%): 1 ≤ N ≤ 2 000.

Subtask 3 (20%): 1 ≤ N ≤ 500 000, A will be in ascending order.

Subtask 4 (34%): 1 ≤ N ≤ 500 000.

Subtask 5 (0%): Sample Testcases

Sample Testcase 1

Input

3
2 1 3

Output

9

Explanation

The possible selections are [2], [1], [3], [2, 1], [1, 3], [2, 1, 3] with minimums 2, 1, 3, 1, 1, 1 respectively.

Therefore the answer is (2 + 1 + 3 + 1 + 1 + 1) = 9.

Sample Testcase 2

Input

8
5 4 8 1 2 6 7 3

Output

85