Problem Brief

Sum of System Vulnerability

NEW GRADOA

See Amazon online assessment and hiring insights

An application at Amazon is deployed on n servers connected linearly. The vulnerability of the ith server is given by vulnerability[i]. The system vulnerability of a contiguous segment of servers is a subsegment defined as the product of the number of servers and the maximum vulnerability of the servers in the segment.

Given the array vulnerability, find the sum of the system vulnerability of all the segments of the servers. Since the answer can be large, report it modulo 10^9 + 7.

ᥫ᭡。spike carries again! ฅ՞•ﻌ•՞ฅ

1Example 1

Input

vulnerability = [3, 2, 3]

Output

Explanation

The sum of all system vulnerabilities is 3 + 6 + 9 + 2 + 6 + 3 = 29.

2Example 2

Input

vulnerability = [4, 2, 1, 2]

Output

Explanation

For each subsegment, calculate the number of servers, maximum vulnerability, and system vulnerability: Subsegment Number of servers Maximum Vulnerability System Vulnerability [4] 1 4 1 * 4 = 4 [4, 2] 2 4 2 * 4 = 8 [4, 2, 1] 3 4 3 * 4 = 12 [4, 2, 1, 2] 4 4 4 * 4 = 16 [2] 1 2 1 * 2 = 2 [2, 1] 2 2 2 * 2 = 4 [2, 1, 2] 3 2 3 * 2 = 6 [1] 1 1 1 * 1 = 1 [1, 2] 2 2 2 * 2 = 4 [2] 1 2 1 * 2 = 2 Sum of system vulnerabilities = 4 + 8 + 12 + 16 + 2 + 4 + 6 + 1 + 4 + 2 = 59

3Example 3

Input

vulnerability = [4, 4]

Output

Explanation

Constraints

Limits and guarantees your solution can rely on.

The first line contains an integer n (1 ≤ n ≤ 10^5) — the number of servers.

The next n lines contain integers vulnerability[i] (1 ≤ vulnerability[i] ≤ 10^5) — the vulnerability of each server.