The goal of this task is, for each two integers ~A~ and ~B~ ~(1 \le A \le B \le N)~, calculate the price of the subsequence ~[A, B]~ of input array ~X~ and to sum up the given values. Let us imagine that we are moving the right bound ~B~ from left to right and maintaining the array of solutions for current ~B~, so that at position ~A~ of that array, call it array ~T~, there is the price of subsequence ~[A, B]~.

A high-level algorithm would look like this:

initialize array T to 0
solution = 0
for B from 1 to N
    subsequences are expanded from [A, B-1] to [A, B] by adding X[B]
    therefore refresh values in array T at positions 1 to B
    add to the solution T[1] + T[2] + … + T[B]

Let's imagine that every member ~T[A]~ of array ~T~ internally contains values ~m~, ~M~ and ~L~, minimal number of sequence ~[A, B]~, maximal number of sequence ~[A, B]~ and length of subsequence ~[A, B]~, respectively.

We need to have an efficient update of values (prices) in array ~T~. Since the value of a member is the product of its internal values, let us observe how these are changing when incrementing ~B~ by ~1~ (moving to the right). Values ~L~ of each member with index smaller than or equal to ~B~ are incremented by ~1~.

Let ~P_m~ be the position of the rightmost member of array ~X~ that is to the left of ~B~ such that it holds ~X[P_m] < X[B]~. Value ~m~ of all members of array ~T~ at position from the interval ~[1, P_m]~ will be left unchanged while the value ~m~ of all members of array ~T~ on positions from the interval ~[P_m+1, B]~ will become exactly ~X[B]~.

Similarly, ~P_M~ be the position of the rightmost member of array ~X~ that is to the left of ~B~ such that it holds ~X[P_M] > X[B]~. Value ~M~ of all members of array ~T~ at position from the interval ~[1, P_M]~ will be left unchanged while the value ~M~ of all members of array ~T~ on positions from the interval ~[P_M+1, B]~ will become exactly ~X[B]~.

Therefore, it is necessary to implement a data structure that will allow the following operations:

• ~\text{increment_L}(lo, hi, d_L)~ - increment value ~L~ by ~d_L~ to all members of the array at position from the interval ~[lo, hi]~.
• ~\text{set_m}(lo, hi, new_m)~ - set value ~m~ to ~new_m~ to all members of the array at position from the interval ~[lo, hi]~.
• ~\text{set_M}(lo, hi, new_M)~ - set value ~M~ to ~new_M~ to all members of the array at position from the interval ~[lo, hi]~.
• ~\text{sum_mML}(lo, hi)~- return the sum of products of values ~m~, ~M~ and ~L~ of all the members of the array at position from the interval ~[lo, hi]~.

It turns out that the required operations can be efficiently achieved using a tournament tree. For this purpose, every node of the tree must contain the following values:

• ~len~ - length of the interval of members of the array that the node is covering, for example, for leaves it holds ~len = 1~
• ~sm~ - sum of values ~m~ of all members from the interval
• ~sM~ - sum of values ~M~ of all members from the interval
• ~sL~ - sum of values ~L~ of all members from the interval
• ~smM~ - sum of values ~m \times M~ of all members from the interval
• ~smL~ - sum of values ~m \times L~ of all members from the interval
• ~sML~ - sum of values ~M \times L~ of all members from the interval
• ~smML~ - sum of values ~m \times M \times L~ of all members from the interval

How would incrementing values ~L~ to all members from the interval belonging to the node of the tree look like?

It is necessary to suitably change the value of each node in the following way:

$$\displaystyle \begin{align*} sL &= sL + d_L \times len \\ smL &= smL + sm \times d_L \\ sML &= sML + sM \times d_L \\ smML &= smML + smM \times d_L \end{align*}$$

Let's observe how setting values ~m~ to all members from the interval belonging to the node of the tree looks like:

$$\displaystyle \begin{align*} sm &= new_m \times len \\ smM &= new_m \times sM \\ smL &= new_m \times sL \\ smML &= new_m \times sML \end{align*}$$

And, finally, setting values ~M~ to all members from the interval belonging to the node of the tree:

$$\displaystyle \begin{align*} sM &= new_M \times len \\ smM &= new_M \times sm \\ smL &= new_M \times sL \\ smML &= new_M \times smL \end{align*}$$

Because of the fact that all values in the nodes are sums, merging two nodes of a child for the purpose of calculating values of the parent node is simply the summation of the corresponding values from both nodes.

The nature of mentioned operations on the structure is such that it is necessary to use tournament tree with propagation. The details of this expansion are general and left out from this description, but can be looked up in the attached code.

We are still left with efficiently finding the rightmost smaller or larger number than the current ~X[B]~. This can be simply implemented using a stack. Here we will describe finding the rightmost smaller value that is to the left of ~X[B]~, and finding the rightmost larger value is done in a similar manner.

If we take into consideration that ~B~ is being moved from left to right, from ~1~ to ~N~, then we are actually talking about the last member of array ~X~ that we passed, and is smaller than ~X[B]~. For each ~B~ from the stack, we will pop all the numbers larger than or equal to ~X[B]~ since from now on they can't ever be someone's last smaller number (~X[B]~ is smaller than them and is located after them). After that, the stack's peak will be exactly the member of array ~X~ that we were looking for, the last one smaller than ~X[B]~. Before incrementing ~B~ and moving to the right, we push ~X[B]~ on the stack. The given algorithm is of linear complexity because each member of the array is pushed and popped from the stack at most once.

All operations on tournament tree are of the complexity ~\mathcal O(\log N)~, and they are done ~\mathcal O(N)~ times, so the total complexity of this solution is ~\mathcal O(N \log N)~.