C. 才羽绿的难题

Problem C. 才羽绿的难题

题目英文名：midori

时空限制：1s/256MB

题目描述：

作为千年学园游戏开发部的成员，才羽绿和才羽桃井自然也要学习信息竞赛。

早上，绿看到桃井正在做一道非常简单的练习题：

“这不是早上刚讲过的□□□□算法（此处信息已被小钩晴删除）的模板题吗！”绿想到，“姐姐应该不能不会做吧。”但她却看到桃井写了一个 的暴力：对每个子区间从左往右暴力访问，求出最大值：

for (int i = 1; i + m - 1 <= n; ++i) {
    int Max = -1;
    for (int j = i; j <= i + m - 1; ++j)
        if (a[j] > Max)
            Max = a[j]; // !
    cout << Max << endl;
}

绿顿时感到眼前一黑，可见早上姐姐根本没听课，一定不知道和谁一起跑去游戏厅了。不过绿也想到一个有趣的问题：对于所有长度为的子区间，暴力求出最大值的时候，最大值会被更新多少次呢，也就是说，上文的代码中带感叹号注释的一行会被执行多少次呢？

输入格式：

第一行输入两个正整数和

第二行输入个正整数表示序列

输出格式：

输出一行个数，表示每个长度为的子区间会发生多少次最大值更新

输入样例：

7 3
1 1 4 5 1 4 4

输出样例：

2 3 2 1 2

样例解释：

画下划线的位置表示发生了最大值更新

第个区间，更新次

第个区间，更新次

第个区间，更新次

第个区间，更新次

第个区间，更新次

数据范围：

对于30%的数据，

对于60%的数据，数据随机生成

对于100%的数据，

小桃：（点提交）啊咧怎么只有30分？苦呀西！