在计算机科学中，二叉搜索树（Binary Search Tree）是一种二叉树，其中每个节点都关联一个键值；节点的键值大于其左子树中所有节点的键值，且小于其右子树中所有节点的键值。二叉搜索树常用于实现动态集合，支持数据的插入、删除以及查找操作。

当从一组键值中查找特定键值时，二叉搜索树通常比朴素查找算法表现更好，因为在与节点值进行比较并向下进入子树时，我们不需要将该键值与另一侧子树中的所有值进行比较。如果二叉搜索树是平衡的，则平均比较次数与树的大小呈对数关系。然而，如果树不平衡，其效果就不那么理想；在极端情况下，时间复杂度会退化为线性。恶意攻击者可能会通过精心构造糟糕的键值插入序列来利用这一漏洞。如果二叉搜索树不是自平衡的，生成的树可能会出现偏差，从而显著降低应用程序的性能。

考虑这样一种场景：你运行的服务器维护着一个由二叉搜索树实现的动态集合。该二叉搜索树采用简单的插入算法，即在不移动现有节点的情况下，将键值作为新叶子节点插入到适当的位置。图 1 展示了如何使用这种简单的插入算法将新键值插入到二叉搜索树中。

图 1：简单插入算法的运行示例。

现在，客户端准备向服务器发送一串键值流，服务器将逐个插入这些键值。你可以重新排列特定范围内的插入顺序，使得生成的树尽可能平衡。请计算在重新排列部分插入顺序后，生成的树中所有节点深度之和的最小值。节点的深度定义为从该节点到根节点的路径上的节点数。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示要插入的键值数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)，表示按顺序插入的键值。所有插入的键值均不相同。 第三行包含两个整数 $l, r$ ($1 \le l \le r \le n, r - l + 1 \le 200$)，表示你可以重新排列的插入范围，即你可以对键值序列 $a_l, a_{l+1}, \dots, a_r$ 进行全排列。

输出格式

输出一行一个整数，表示生成的二叉搜索树中所有节点深度之和的最小值。

样例

样例输入 1

8
2 4 5 7 1 3 8 6
3 6

样例输出 1

24

样例输入 2

5
5 1 2 3 4
3 5

样例输出 2

14

样例输入 3

7
3 2 4 6 7 5 1
1 7

样例输出 3

17

说明

对于第一组样例数据，重排后的一种最优插入序列为 $[2,4,1,7,3,5,8,6]$。生成的二叉搜索树如图 2 所示。

图 2：第一组样例数据中的最优二叉搜索树。