Key Management

In computer science, a binary search tree is a binary tree where each node is associated with a key. The key of a node is greater than all keys in its left subtree but smaller than all keys in its right subtree. Binary search trees are commonly used to implement dynamic sets, which support inserting or deleting data items, as well as searching for them.

When searching for a specific key in a set of keys, a binary search tree usually performs better than the naive search algorithm. When comparing with the value in a node and walking down into a subtree, we do not need to compare the key with the values in the other subtree. The average number of comparisons is logarithmic in the size of the tree if the tree is balanced. However, it is not so effective if the tree is unbalanced. In extreme cases, the time complexity degenerates to linear. Malicious attackers may exploit this weakness by crafting a bad key insertion sequence. If the binary search tree is not self-balancing, the resulting tree may be skewed, which hurts the performance of the application.

Consider a server that maintains a dynamic set implemented by a binary search tree. The binary search tree uses a simple insertion algorithm, which inserts the key as a new leaf in the appropriate position without moving existing nodes. Figure 6 shows how a new key is inserted into a binary search tree using this simple insertion algorithm.

(a) Before insertion	(b) After insertion

Figure 6: A running example of the simple insertion algorithm.

Now a client sends a stream of keys to the server, and the server inserts the keys one by one. You are allowed to reorder a specific range of insertions so that the resulting tree is as balanced as possible. Report the minimum possible sum of depths of the nodes in the resulting tree after reordering part of the insertions. The depth of a node is the number of nodes on the path from that node to the root.

The first line contains a single integer $n$ $(1 \leq n \leq 10^5)$, the number of keys to insert.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ $(1 \leq a_i \leq n)$, the keys to insert in order. All inserted keys are distinct.

The third line contains two integers $l$ and $r$ $(1 \leq l \leq r \leq n, r - l + 1 \leq 200)$, the range of insertions you can reorder. You can permute the insertions of keys $a_l, a_{l+1}, \cdots, a_r$.

Output a single integer in one line, the minimum possible sum of depths of the nodes in the resulting binary search tree.

For the first sample, one optimal insertion sequence after rearrangement is [2,4,1,7,3,5,8,6]. The resulting binary search tree is shown in Figure 7.

Figure 7: The optimal binary search tree for the first sample.