Recently I got stuck in a problem. The part of algorithm requires to compute sum of maximum element of sliding windows of length **K**. Where **K** ranges from ***1<=K<=N*** (N length of an array).

Example if I have an array A as `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 is 24,29,24,12`.  

I have tried to this **O(N^2)**. For each sliding window of length **K**, I can calculate the maximum in O(N). Since K is upto N. Therefore, overall complexity turns out to be **O(N^2)**.  

I am looking for **O(N)** or **O(NlogN)** or something similar to this algorithm as N maybe upto 10^5.   

***Note:*** Elements in array can be as large as **10^9** so output the final answer as modulo *10^9+7*

***EDIT: What I actually want to find answer for each and every value of K (i.e. from 0 to N) in overall linear time or in O(NlogN) not in O(KN) or O(KNlogN) where K={1,2,3,.... N}***