1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>

using namespace std;

struct triple {
	int a,b,id;
	triple(int a, int b, int id) : a(a), b(b), id(id) {}
};

bool compareTriple(triple t1, triple t2) {
	return t1.a < t2.a || (t1.a == t2.a && t1.b > t2.b);
}

int n, k, q;
// vector<int> l, r;
vector<triple> to_sort;

int a[300001];
long long sumy[300001];
long long wyn[300001];
long long final_out[300000];

deque<long long> maxes;

void process_from_l_to_r(int l, int r) {
	long long currentMax = 0L;
	maxes.clear();
	for(int i = l; i < l+k-1; i++) {
		wyn[i] = 0L;
	}
	for(int i=l + k -1; i <= r; i++) {
		long long prevMax = 0L;
		if (maxes.size() >= k) {
			prevMax = maxes.front();
			maxes.pop_front();
		}
		long long currWyn = sumy[i] + prevMax;
		// cout << i << ": " << currWyn << endl;
		if (currWyn > currentMax) {
			currentMax = currWyn;
		}
		wyn[i] = currentMax;
		maxes.push_back(currentMax);
	}
}

int main() {
	ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k >> q;
    for(int i = 1; i <= n; i++) {
    	cin >> a[i];
    }
    for(int i = 0; i < q; i++) {
    	int b1, b2;
    	cin >> b1 >> b2;
    	// l.push_back(b1);
    	// r.push_back(b2);
    	to_sort.push_back(triple(b1, b2, i));
    }
    sort(to_sort.begin(), to_sort.end(), compareTriple);
    // cout << "dupa1\n";

    long long s=0L;
    for(int i=1; i <= k; i++) {
    	s += a[i];
    }
    if (s > 0) {
    	sumy[k] = s;
	}
    for(int i = k+1; i <= n; i++) {
    	s = s + a[i] - a[i-k];
    	sumy[i] = s;
    	if (s < 0) { 
    		sumy[i] = 0L;
    	}
    }

    int prev_start=0;
    for(int i=0; i < to_sort.size(); i++) {
    	if (to_sort[i].a != prev_start) {
    		// cout << "PROCESS " << to_sort[i].a << " " << to_sort[i].b << endl;
    		process_from_l_to_r(to_sort[i].a, to_sort[i].b);
    		prev_start = to_sort[i].a;
    	}
    	final_out[to_sort[i].id] = wyn[to_sort[i].b];
    }

    for(int i = 0; i < q; i++) {
    	cout << final_out[i] << endl;
    }

	return 0;
}