Soma dos Máximos de Janelas
Dado um array $A$ de $N$ inteiros e um inteiro $K$, considere todas as janelas contíguas de tamanho exatamente $K$: $A[1..K],\ A[2..K+1],\ \ldots,\ A[N-K+1..N]$.
Calcule a soma dos máximos de todas essas janelas.
Input
A primeira linha contém dois inteiros $N$ e $K$ $(1 \le K \le N \le 10^6)$.
A segunda linha contém $N$ inteiros $A_i$ $(-10^9 \le A_i \le 10^9)$.
Output
Imprima um único inteiro: a soma dos máximos de todas as janelas de tamanho $K$.
7 3 1 3 -1 -3 5 3 6
22
Explanation 1:
| Janela | Máximo |
|---------------|--------|
| $[1, 3, -1]$ | $3$ |
| $[3, -1, -3]$ | $3$ |
| $[-1, -3, 5]$ | $5$ |
| $[-3, 5, 3]$ | $5$ |
| $[5, 3, 6]$ | $6$ |
Soma: $3 + 3 + 5 + 5 + 6 = 22$.
5 2 4 2 7 1 9
27
Explanation 2:
Máximos das janelas: $\max(4,2)=4$, $\max(2,7)=7$, $\max(7,1)=7$, $\max(1,9)=9$. Soma $= 27$.
4 2 -5 -3 -7 -2
-8