634. Sum of subarray minimum

0

Medium

Rohit wants to solve a subarray problem. So he picks a problem and stucks in it . He needed your help in this problem. You are given an array of integers ***nums*** of size **n**. Find the sum of min(b), where b ranges over every (contiguous) subarray of **nums**. Since the answer may be large, Print the answer modulo 109 + 7.

Input Format

First line contains an integer N(size of array) .
Second line contains an integer array.

Output Format

Print the answer.

Example

Input

4 3 1 2 4

Output

17

Constraints

1 <= n <= 104
1 <= nums[i] <= 104
Loading...

View Submissions

Console