algorithm - sum of maximum element of sliding window of length K -

recently got stuck in problem. part of algorithm requires compute sum of maximum element of sliding windows of length k. k ranges 1<=k<=n (n length of array).

example if have array 5,3,12,4
sliding window of length 1: 5 + 3 + 12 + 4 = 24
sliding window of length 2: 5 + 12 + 12 = 29
sliding window of length 3: 12 + 12 = 24
sliding window of length 4: 12

final answer 24,29,24,12.

have tried o(n^2). each sliding window of length k, can calculate maximum in o(n). since k upto n. therefore, overall complexity turns out o(n^2).
looking o(n) or o(nlogn) or similar algorithm n maybe upto 10^5.
note: elements in array can large 10^9 output final answer modulo 10^9+7

edit: want find answer each , every value of k (i.e. 0 n) in overall linear time or in o(nlogn) not in o(kn) or o(knlogn) k={1,2,3,.... n}

here's abbreviated sketch of o(n).

for each element, determine how many contiguous elements left no greater (call a), , how many contiguous elements right lesser (call b). can done elements in time o(n) -- see mbo's answer.

a particular element maximum in window if window contains element , elements among a left , b right. usefully, number of such windows of length k (and hence total contribution of these windows) piecewise linear in k, @ 5 pieces. example, if a = 5 , b = 3, there are

1 window  of size 1 2 windows of size 2 3 windows of size 3 4 windows of size 4 4 windows of size 5 4 windows of size 6 3 windows of size 7 2 windows of size 8 1 window  of size 9. 

the data structure need encode contribution efficiently fenwick tree values not numbers linear functions of k. each linear piece of piecewise linear contribution function, add cell @ beginning of interval , subtract cell @ end (closed beginning, open end). @ end, retrieve of prefix sums , evaluate them @ index k final array.

(ok, have run now, don't need fenwick tree step two, drops complexity o(n) that, , there may way step 1 in linear time well.)

python 3, lightly tested:

def left_extents(lst):   result = []   stack = [-1]   in range(len(lst)):     while stack[-1] >= 0 , lst[i] >= lst[stack[-1]]:       del stack[-1]     result.append(stack[-1] + 1)     stack.append(i)   return result   def right_extents(lst):   result = []   stack = [len(lst)]   in range(len(lst) - 1, -1, -1):     while stack[-1] < len(lst) , lst[i] > lst[stack[-1]]:       del stack[-1]     result.append(stack[-1])     stack.append(i)   result.reverse()   return result   def sliding_window_totals(lst):   delta_constant = [0] * (len(lst) + 2)   delta_linear = [0] * (len(lst) + 2)   l, i, r in zip(left_extents(lst), range(len(lst)), right_extents(lst)):     = - l     b = r - (i + 1)     if > b:       a, b = b,     delta_linear[1] += lst[i]     delta_linear[a + 1] -= lst[i]     delta_constant[a + 1] += lst[i] * (a + 1)     delta_constant[b + 2] += lst[i] * (b + 1)     delta_linear[b + 2] -= lst[i]     delta_linear[a + b + 2] += lst[i]     delta_constant[a + b + 2] -= lst[i] * (a + 1)     delta_constant[a + b + 2] -= lst[i] * (b + 1)   result = []   constant = 0   linear = 0   j in range(1, len(lst) + 1):     constant += delta_constant[j]     linear += delta_linear[j]     result.append(constant + linear * j)   return result  print(sliding_window_totals([5, 3, 12, 4]))