Sum of Maximum of continuous blocks of length k
For an appropriate data structure $D$, which maintains the last $k$ elements, it is natural to consider the following solution:


Initialize $D$ with $A_1,\ldots,A_k$, and initialize the sum $S$ with $\max D$.
For $i=k+1,\ldots,n$:


Remove $A_{i-k}$ from $D$.
Add $A_i$ to $D$.
Add $\max D$ to $S$.

Return $S$.


The data structure has to support three kinds of operations:


Adding an element.
Removing an element.
Calculating the maximum.


I'll let you figure out what data structure is most suitable, and what is the resulting complexity.