Compute Beauty of Array Products

For each contiguous window of length k, count the positions that are strictly greater than every later element in the window, then add these counts over all windows. The last position of a window counts because it has no later element.

Added by this site: the first line of standard input contains n k and the second line contains n integers; 1≤n≤200000, 1≤k≤n, −10^9≤products[i]≤10^9.

输入格式

The first line contains n k, and the second line contains n integers products[i].

Added by this site: the first line of standard input contains n k and the second line contains n integers; 1≤n≤200000, 1≤k≤n, −10^9≤products[i]≤10^9.

输出格式

Output the total beauty of all windows of length k.

样例 1

输入：

6 3
3 6 2 9 4 1

输出：

8