Sum of Maximum Elements in Subarrays

You are given an array of N integers and an integer K. Your task is to compute the sum of the maximum elements of all contiguous subarrays of length K.

More formally, let the array be \(a_1, a_2, \ldots, a_N\). For every contiguous subarray \(a_i, a_{i+1}, \ldots, a_{i+K-1}\) (where \(1 \le i \le N-K+1\)), determine the maximum element and compute its sum. That is, output the value:

[ \sum_{i=1}^{N-K+1} \max(a_i, a_{i+1}, \ldots, a_{i+K-1}) ]

Note: You must consider the subarrays in order and process the input from standard input (stdin) and output the result to standard output (stdout).

inputFormat

The first line contains two integers N and K (\(1 \le K \le N \le 10^5\)), where N is the number of elements in the array, and K the subarray length.

The second line contains N space-separated integers denoting the elements of the array.

outputFormat

Output a single integer, the sum of the maximum elements of all contiguous subarrays of length K.

7 3
5 1 3 2 6 4 8

28