Codeforces Round 211 (Div. 2)
B
Fence
Codeforces
1100
原题
← AC →
翻译中…

There is a fence in front of Polycarpus's home. The fence consists of $*n*$ planks of the same width which go one after another from left to right. The height of the $*i*$-th plank is $*h*_{*i*}$ meters, distinct planks can have distinct heights.

翻译中…

image Fence for $*n* = 7$ and $*h* = [1, 2, 6, 1, 1, 7, 1]$

翻译中…

Polycarpus has bought a posh piano and is thinking about how to get it into the house. In order to carry out his plan, he needs to take exactly $*k*$ consecutive planks from the fence. Higher planks are harder to tear off the fence, so Polycarpus wants to find such $*k*$ consecutive planks that the sum of their heights is minimal possible.

翻译中…

Write the program that finds the indexes of $*k*$ consecutive planks with minimal total height. Pay attention, the fence is not around Polycarpus's home, it is in front of home (in other words, the fence isn't cyclic).

翻译中…

Input

翻译中…

The first line of the input contains integers $*n*$ and $*k*$ ($1 ≤ *n* ≤ 1.5·10^{5}, 1 ≤ *k* ≤ *n*$) — the number of planks in the fence and the width of the hole for the piano. The second line contains the sequence of integers $*h*_{1}, *h*_{2}, ..., *h*_{*n*}$ ($1 ≤ *h*_{*i*} ≤ 100$), where $*h*_{*i*}$ is the height of the $*i*$-th plank of the fence.

翻译中…

Output

翻译中…

Print such integer $*j*$ that the sum of the heights of planks $*j*$, $*j* + 1$, ..., $*j* + *k* - 1$ is the minimum possible. If there are multiple such $*j*$'s, print any of them.

翻译中…

Note

翻译中…

In the sample, your task is to find three consecutive planks with the minimum sum of heights. In the given case three planks with indexes 3, 4 and 5 have the required attribute, their total height is 8.

翻译中…

样例

Input #1
7 3
1 2 6 1 1 7 1
Output #1
3
InputCopy OutputCopy
题目信息
题号
363B
时间限制
1 s
内存限制
256 MB
标签
暴力
动态规划

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。