Maximizing Contiguous Segment Profit

You are given a stone divided into n sections. Each section has an integer value representing its worth. Your task is to determine the maximum possible profit that can be obtained by mining a contiguous segment of sections, with the condition that the length of the segment is at least k and at most l sections.

Formally, if the stone's sections are denoted by an array \(A\) of length \(n\), you need to find indices \(i\) and \(j\) (with \(1 \leq i \leq j \leq n\)) such that \(j-i+1 \in [k,l]\) and the sum

[ S = \sum_{t=i}^{j} A_t ]

is maximized. If all segments have negative sums, the maximum profit would be the least negative value (i.e. the maximum single element if segment lengths are forced by constraints).

Note: Use the properties of prefix sums to optimize your solution if necessary.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains an integer n, the number of sections.
2. The second line contains n space-separated integers, representing the worths of each section.
3. The third line contains two space-separated integers k and l which represent the minimum and maximum length of the mining segment respectively.

outputFormat

Output a single integer to stdout which is the maximum possible profit as defined above.

8
4 -1 2 1 6 -3 3 4
3 5

12