Description

给一个长度为n的序列，第i个数为a[i],将这个序列划分成i个不重复的子串，从每个子串中取出j个数作为分割价值。方法价值为val(I,j)。

Format

Input

输入一个n；(1<=n<=1e6)

第二行输入n个数；

第三行输入x,y;(1<x,y<=n)

Output

输出一个数，为所求答案。

Samples

5
6 4 4 5 3
2 2

47

Hint

val(1,1)=6 ，分割成 [6,4,4,5,3]，最大的数是 6

val(1,2)=11，分割成 [6,4,4,5,3]，最大的两个数是 6 和 5

val(2,1)=11，分割成 [6,4][4,5,3]，两组中各自最大的数是 6 和 5

val(2,2)=19，分割成 [6,4][4,5,3]，两组中各自最大的两个数是 6,4 和 5,4

故答案为6+11+11+19=47