TOI12: Barrier

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

using lli = long long;
using pli = pair<lli, int>;

int main(){

    int n, lim;
    scanf("%d", &n);
    scanf("%d", &lim);

    vector<lli> qs(n + 1, 0);
    for(int i = 1; i <= n; ++i){
        scanf("%lld", &qs[i]);
        qs[i] += qs[i - 1];
    }

    lli mx = -1e18;
    int mnlen = lim;
    vector<lli> dp(n + 1, 0);
    deque<pli> q;
    for(int i = 1; i <= n; ++i){
        while(!q.empty() && q.back().first <= -qs[i - 1]){
            q.pop_back();
        }
        q.push_back(make_pair(-qs[i - 1], i));
        while(!q.empty() && q.front().second < i - lim + 1){
            q.pop_front();
        }
        dp[i] = qs[i] + q.front().first;
        if(dp[i] > mx){
            mx = dp[i];
            mnlen = i - q.front().second + 1;
        } else if(dp[i] == mx){
            mnlen = min(mnlen, i - q.front().second + 1);
        }
    }

    if(mx <= 0){
        cout << 0 << "\n" << 0;
    } else {
        cout << mx << "\n" << mnlen;
    }

    return 0;
}