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.


-----Examples-----
Input
7 3
1 2 6 1 1 7 1

Output
3



-----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.

Difficulty: interview

Starter code:

Solutions:
n, k = map(int, input().split())
h = list(map(int, input().split()))
a = [0]*(n-k+1)
a[0] = sum(h[0:k])
for i in range(1,n-k+1):
    a[i] = a[i-1]+h[i+k-1]-h[i-1]
m = min(a)
print(a.index(m)+1)

#Fence

data = input().split(" ")
n = int(data[0])
k = int(data[1])
minIndex = 1
minCost = 0
heights = input().split(" ")
heights = [int(x) for x in heights]
for j in range(k):
	minCost += heights[0+j]

cost = minCost
for i in range(1,len(heights)-k+1):
	cost = cost - heights[i-1] + heights[i+k-1]
	if cost < minCost:
		minCost = cost
		minIndex = i+1
print(minIndex)

n, k = list(map(int, input().split()))
A = list(map(int, input().split()))
B = [0] * n
Sum = 0
for i in range(len(A)):
    Sum += A[i]
    B[i] = Sum
Min = 10e10
ind = 0
B = [0] + B
for i in range(1, n - k + 2):
    x = B[i + k - 1] - B[i - 1]
    if x < Min:
        Min = x
        ind = i
print(ind)


N, K = input().split()
N, K = int(N), int(K)
planks = tuple(map(int, input().split()))
min_poss = 999999999
sum_array = sorted(planks)
sum_array[K-1] = sum(planks[:K])
for i in range(K,N):
    sum_array[i] = cur = sum_array[i-1]+planks[i]-planks[i-K]
print(sum_array.index(min(sum_array[K-1:]))-K + 2)


n, k = map(int, input().split())
h = list(map(int, input().split()))
ans = [0]*(n-k+1)
#for i in range(k):
#    h.append(10**9)
ans[0]= sum(h[:k])
minim = ans[0]
aminim = 0
for i in range(1,n-k+1):
    ans[i] = ans[i-1]+h[i+k-1]-h[i-1]
    if ans[i] < minim:
        minim = ans[i]
        aminim = i
print(aminim+1)

n,k=list(map(int,input().split()))


L=list(map(int,input().split()))

s=sum(L[0:k])

ind=0
minn=s
ans=0
for i in range(k,n):
    s+=L[i]
    s-=L[ind]
    ind+=1
    if(s<minn):
        minn=s
        ans=ind
print(ans+1)


3

def readln(): return tuple(map(int, input().split()))

n, k = readln()
h = readln()
ans = s = sum(h[:k])
j = 1
for _ in range(k, n):
    s += -h[_ - k] + h[_]
    if ans > s:
        ans = s
        j = _ - k + 2
print(j)


n,k = list(map(int, input().split()))
a=list(map(int,input().split()))
t=0
result=0
for i in range(0,k):
    t+=a[i]
    result+=a[i]
index=0
for i in range(k,n):
    t+=a[i]
    t-=a[i-k]
    if result>t:
        result=t
        index=i-k+1
print(index+1)


def readInput():
    return [int(x) for x in input().split()]

inputdata = readInput()
data = readInput()

n = inputdata[0]
k = inputdata[1]

sums = list(range(n))
for i in range(n):
    sums[i] = data[i]
    if (i > 0):
        sums[i] += sums[i - 1]

index = -1
minVal = -1

i = 0
while i + k - 1 <= n - 1:
    if (index == -1):
        index = 0
        minVal = sums[k - 1]
    else:
        curr = sums[i + k - 1] - sums[i - 1]
        if (curr < minVal):
            minVal = curr
            index = i
    i += 1

print(index + 1)


n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[a[0]]
for i in range(1,n):
    b.append(b[i-1]+a[i])
mina=b[k-1]
x=k-1
for i in range(k,n):
    if b[i]-b[i-k]<mina:
        x=i
        mina=b[i]-b[i-k]
print(x-k+2)

n, k = map(int, input().split())
t = list(map(int, input().split()))
for i in range(n - 1):
    t[i + 1] += t[i]
t = [0] + t
print(min((t[i + k] - t[i], i) for i in range(n - k + 1))[1] + 1)

n,m = list(map(int,input().split()))
num = [int(x) for x in input().split()]
Min = Sum = Pos = 0
for i in range(m):
    Sum += num[i]
Min = Sum
for i in range(m,n):
    Sum += num[i]-num[i-m]
    if Min > Sum:
        Min = Sum
        Pos = i-m+1
print(Pos+1)


n,m = list(map(int,input().split()))
num = [int(x) for x in input().split()]
for i in range(n-1): num[i+1]+=num[i]
num.insert(0,0)
print(min((num[i+m]-num[i],i) for i in range(n-m+1))[1]+1)



def actions(n, k, h):
	j = 0

	smin = sum([h[x] for x in range(0, k)])
	last = smin

	for i in range(1, n-k+1):
		s = last - h[i-1] + h[i+k-1]
		last = s
		if s<smin:
			smin = s
			j = i

	return j+1

def main():
	n,k = list(map(int, input().split()))
	h = list(map(int, input().split()))

	print(actions(n,k,h))

def __starting_point(): main()
__starting_point()

#! /usr/bin/env python

n, k = input().split()
n = int(n)
k = int(k)
f = [int(x) for x in input().split()]
tmp = 0
for i in range(k):
    tmp += f[i]
mini = tmp
pos = 0
for i in range(k, n):
    tmp += f[i] - f[i - k]
    if tmp < mini:
        mini = tmp
        pos = i - k + 1;
print(pos + 1)


n, k = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]

s = sum(l[0:k])
t = s
ind=1
for i in range(k, n):
	t -=l[i-k]
	t +=l[i]
	if t<s:
		s = t
		ind = i-k+2
print(ind)


__author__ = 'asmn'
n, k = tuple(map(int, input().split()))
h = [0] + list(map(int, input().split()))

for i in range(1, n + 1):
    h[i] += h[i - 1]

s = [h[i] - h[i - k] for i in range(k, n + 1)]

print(s.index(min(s)) + 1)

n,k=list(map(int,input().split()))

z=[int(x) for x in input().split()]

pref=[0]
for i in range (1,n+1):
    pref.append(z[i-1]+pref[i-1])

##print (pref[:])
minsum=1000000000
minind=1

for j in range (1,n-k+2):
    if (pref[j+k-1]-pref[j-1]<minsum):
        minsum=pref[j+k-1]-pref[j-1]
        minind=j
    else:
        continue


print (minind)


n, k = map(int, input().split())
h = list(map(int, input().split()))
s = [0] * (n + 1)
for i in range(n):
  s[i + 1] = s[i] + h[i]
x = 0
y = s[-1]
for i in range(n - k + 1):
  if s[i + k] - s[i] < y:
    x = i
    y = s[i + k] - s[i]
print(x + 1)

n, k = input().split(' ')
a = input().split(' ')
sum = 0
for i in range(0, int(k)):
    sum += int(a[i])
res = sum
ans = 0
for i in range(int(k), int(n)):
    sum += int(a[i])
    sum -= int(a[i-int(k)])
    if sum < res:
        res = sum
        ans = i - int(k) + 1
print(ans + 1)


minimum = pow(10, 19)
index = 0

n, k = list(map(int, input().split(' ')))
fence = list(map(int, input().split(' ')))

if k!=1:
    dp = [0]+[fence[0]]+[0]*(n-1)
    for t in range(2, n+1):
        dp[t] = dp[t-1]+fence[t-1]

    for u in range(n-k+1):
        value = dp[u+k]-dp[u]
        if value < minimum:
            index = u
            minimum = value

    print(index+1)

else:
    print(fence.index(min(fence))+1)


minimum = pow(10, 19)
index = 0

n, k = list(map(int, input().split(' ')))
fence = list(map(int, input().split(' ')))


dp = [0]+[fence[0]]+[0]*(n-1)
for t in range(2, n+1):
    dp[t] = dp[t-1]+fence[t-1]

for u in range(n-k+1):
    value = dp[u+k]-dp[u]
    if value < minimum:
        index = u
        minimum = value

print(index+1)


n, k = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]
s = sum(h[: k])
res = s
pos = 0
for i in range(n - k):
	s += h[i + k] - h[i]
	if s < res:
		res = s
		pos = i + 1
print(pos + 1)


def main():
    n, k = map(int, input().split())
    hh = list(map(int, input().split()))
    s = sum(hh[:k])
    l = [s]
    for a, b in zip(hh, hh[k:]):
        s = s + b - a
        l.append(s)
    print(min(range(len(l)), key=l.__getitem__) + 1)


def __starting_point():
    main()
__starting_point()