F. Double-Ended Queue
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Gunga just learned what a double-ended queue is in his data structure class. a double-ended queue (deque) is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail).

Now, he is playing with his own double-ended queue. He has an empty double-ended queue $$$B$$$ and an array of integers $$$A$$$. In the $$$i$$$-th move, he will add $$$A_i$$$ to one end of $$$B$$$. His goal is to maximize the sum of values from $$$B_L$$$ to $$$B_R$$$, inclusively. $$$B_i$$$ is defined as the $$$i$$$-th element in the deque from the front.

Formally, find the maximum value over all possible $$$B$$$ formed in the end:

$$$$$$\sum_{i=L}^R B_i$$$$$$

Input

The first line contains an integer $$$n,L,R$$$ $$$(1 \leq n \leq 2 \times 10^5,1\le L\le R\le n)$$$ – the number of integers and Gunga's favorite interval.

The second line contains $$$n$$$ space-separated integers $$$A_1, A_2, \ldots, A_n$$$ $$$(-10^9 \leq A_i \leq 10^9)$$$.

Output

Output the maximum sum from $$$B_L$$$ to $$$B_R$$$.

Examples
Input
5 1 3
1 2 3 4 5
Output
12
Input
10 2 5
3 21 4 2 48 32 12 10 5 9
Output
113