Challenge: Busiest Stretch

Lab Java Beginner 10 points

A café counted customers each hour for n hours. Find the k hours in a row with the most customers. Print the starting hour (from 0) and the total. If several stretches tie, print the earliest. Use a sliding window.

Input

Line 1: n k (1 ≤ k ≤ n). Line 2: n whole numbers.

Output

<start> <total>

Example

Input

8 3
2 5 1 8 7 3 9 1

Output

4 19

Sample input available Sample output available

Editor

Java

Hints

Total the first k hours, then slide: add a[end], subtract a[end - k].

Only replace the best when the new total is strictly bigger, so the earliest stretch wins ties.

Solution explanation

One addition and one subtraction per hour: O(n), whatever the size of k.

Show solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        long window = 0;
        for (int i = 0; i < k; i++) window += a[i];
        long best = window;
        int start = 0;
        for (int end = k; end < n; end++) {
            window += a[end] - a[end - k];
            if (window > best) {
                best = window;
                start = end - k + 1;
            }
        }
        System.out.println(start + " " + best);
    }
}

Output

Answer