Show problems as
Classic problem #2281HardArrayStackMonotonic StackPrefix Sum

Sum of Total Strength of Wizards

Real-world version: Total Yield of Every Turbine Stretch
Tracked in this browser only
Read Sum of Total Strength of Wizards on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A wind farm has its turbines standing in a single row. rating[i] is the output rating of the turbine at position i.

A stretch is any non-empty run of turbines at consecutive positions. The yield of a stretch is the smallest rating inside it multiplied by the total of all ratings inside it.

Audit every stretch of the row and return the sum of their yields. Stretches are identified by the positions they cover, so two stretches covering different positions are both counted even when their ratings happen to match.

The sum grows far past machine word size, so return it modulo 1000000007.

Examples

Example 1

Input
rating = [7, 3, 8]
Output
239

The six stretches yield `7*7 = 49`, `3*3 = 9`, `8*8 = 64`, `3*10 = 30`, `3*11 = 33` and `3*18 = 54`, and those add up to 239, which is already below the modulus.

Example 2

Input
rating = [6, 6, 2, 9]
Output
375

The four single-turbine stretches yield 36, 36, 4 and 81. The adjacent pairs yield `6*12 = 72`, `2*8 = 16` and `2*11 = 22`, the triples yield `2*14 = 28` and `2*17 = 34`, and the whole row yields `2*23 = 46`. The total is 375.

Example 3

Input
rating = [1000000000, 1, 1000000000]
Output
74

The two outer turbines each yield `1000000000 * 1000000000` on their own, the middle one yields 1, and the three stretches that include the middle turbine yield `1 * 1000000001`, `1 * 1000000001` and `1 * 2000000001`. The exact total is 2000000004000000004, and the answer is that value modulo 1000000007.

Constraints

  • 1 <= rating.length <= 10^5
  • 1 <= rating[i] <= 10^9
  • Return the sum of all stretch yields modulo 1000000007.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def total_stretch_yield(rating: list[int]) -> int:
Java
public int totalStretchYield(int[] rating)

More on the same topics