#CF363B. 栅栏

栅栏

CF363B Fence

题目描述

\hspace{15pt}在 Polycarpus 家门前有一排栅栏。栅栏由 nn 块宽度相同的木板组成,这些木板从左到右依次排放。第 ii 块木板的高度为 hih_i 米,不同的木板高度可以不同。

\hspace{15pt}当 n=7n=7 且 h={1,2,6,1,1,7,1}h=\{1,2,6,1,1,7,1\} 时的栅栏示意图。

\hspace{15pt}Polycarpus 买了一架高级钢琴,正在思考如何把它搬进家。为此,他需要从栅栏上拆掉连续的 kk 块木板。高度更高的木板更难拆卸,因此 Polycarpus 希望找到一组连续的 kk 块木板,使得它们的高度总和尽可能小。

\hspace{15pt}请编写程序,找出这组总高度最小的连续 kk 块木板的编号。

\hspace{15pt}请注意,栅栏不是围绕 Polycarpus 的房子设立的,只是在门前(换句话说,栅栏不是环状的)。

输入格式

\hspace{15pt}第一行输入两个整数 $n,k \left(1 \leqq n \leqq 1.5 \times 10^5;\ 1 \leqq k \leqq n\right)$ 分别代表栅栏木板的数量和需要拆掉的连续木板数量。

\hspace{15pt}第二行输入 nn 个整数 $h_1,h_2,\dots,h_n \left(1 \leqq h_i \leqq 100\right)$,其中 hih_i 表示第 ii 块木板的高度。

输出格式

\hspace{15pt}在一行上输出一个整数 jj,代表从第 jj 块木板开始的连续 kk 块木板高度总和最小。如果有多个符合条件的答案,输出其中任意一个即可。

测试样例

7 3
1 2 6 1 1 7 1

3

样例 1 解释

\hspace{15pt}需要找到高度和最小的连续 33 块木板。在给定情况下,编号为 3,4,53,4,5 的三块木板高度分别为 6,1,16,1,1,高度和为 88,是所有连续 33 块木板中最小的,因此输出 33。