Cửa sổ chi phí thấp nhất

Bối cảnh và bài toán

Một tuyến gồm n vị trí liên tiếp, mỗi vị trí có chi phí xử lý a[i]. Một thiết bị bắt buộc phải chiếm đúng k vị trí liên tiếp. Cần chọn vị trí bắt đầu sao cho tổng chi phí nhỏ nhất.

Yêu cầu

In chỉ số bắt đầu 1-based của một đoạn đúng k phần tử có tổng nhỏ nhất. Nếu có nhiều đoạn cùng tốt, in đoạn xuất hiện sớm nhất.

Input

• Dòng 1: n k.
• Dòng 2: n số a[i].

Output

In chỉ số bắt đầu của cửa sổ tối ưu.

Ràng buộc

• 1 <= k <= n <= 10^5
• 1 <= a[i] <= 10^9

Chấm điểm

Ví dụ 1

Input

7 3
1 2 6 1 1 7 1

Output

3

Giải thích. Các vị trí 3..5 có tổng 6+1+1=8, là nhỏ nhất.

Ví dụ 2

Input

5 2
5 1 1 5 1

Output

2

Giải thích. Đoạn bắt đầu tại 2 có tổng 2 và là tối ưu.

Thông tin bài tập

Nguồn: Phỏng theo Codeforces 363B — Fence.

Tham khảo: https://codeforces.com/problemset/problem/363/B