题目内容

闹市区中有一条马路，马路从0号路口开始，到 N-1 号路口结束，在每个路口都架设了最新技术的通信基站，每个基站的信号可以覆盖前后各 k 个路口的范围，即第 i 个路口上的基站，可以覆盖 [i-k, i+k] 这两个路口之间的马路，因此用户的手机处于多个基站的覆盖范围中。每个基站会统计当前接入人数，为保障最佳通信质量，用户手机应选择连接人数最少的基站进行通讯。

这条马路一共 N 个路口，小明从0号路口出发向前走，求小明在每个路段中的最佳通讯基站。不考虑处于路口中间的特殊场景，只考虑在每个路段中的场景，例如第1个路段应为0号路口到1号路口之间的路段，如果基站覆盖范围 k=2 ，此时最佳基站应为0、1、2中连接人数最少的基站。

输入描述

输入人为两行

第一行长度为 N 的整数数组 crossroads[] ，数组元素以空格分隔，其中 crossroads[i] 表示 i 号路口基站的当前接入人数。 1 <= crossroads，length数组长度 <= 10^5，0 <= crossroads[i] <= 10^2

第二行为基站覆盖范围 k ， 1 <= k <= crossroads.length

非法输入返回-1

输出描述

返回一个数组 ret ，ret[i] 表示 i 路段上最佳基站的编号，数组元素之间以空格分隔。例如0号路口到1号路口的路段，为0号路段，其最佳基站用 ret[0] 表示。

样例1

输入

3 5 8 7 6 7 4
2

输出

0 0 1 4 6 6

说明

小明在第1段路时，位于0号和1号基站中间，此时可以连接到0、1、2这3个基站，而这三个基站中连接人数最小的是0号基站(3个人)，因此输出数组第一个元素应为0号基站。小明位于第2段路时，位于1号和2号基站中间，此时可以连接到0、1、2、3这4个基站，选择其中连接人数最小的基站，即0号基站(3人)，因此输出数组第二个元素为0号基站。以此类推。

样例2

输入

9 8 7 6 7 8 9
2

输出

2 3 3 3 3 4

说明

小明在第1段路时，可以连接到的基站为0、1、2这3个基站，其中连接人数最小的基站为2号基站(7人连接)，因此输出数组第一个元素为2号基站。以此类推。