划分

题号：NC211539
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给你一个长度为 n 的序列，第 i 个数为 $a_i$

将这个序列分割成 i 个不重合的子串，从每个子串中取出最大的 j 个数作为这个分割方法的价值，记价值最大的分割方法的价值为 val(i,j)

但是金发少女 DK 觉得这太好算了，于是她要你求下面的柿子

$\sum_{i=1}^{x}\sum_{j=1}^{y}val(i,j)$

输入描述:

第一行输入一个正整数 n

第二行输入 n 个正整数，第 i 个数表示 $a_i$

第三行输入两个正整数 x,y，含义如题中所示

输出描述:

一个数，表示答案

示例1

输入

复制

5
6 4 4 5 3
2 2

输出

复制

说明

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

备注:

, ,