Scalar Queries
Contest: Educational Codeforces Round 65 (Rated for Div. 2)
Difficulty rating: 2300
Tags: combinatorics, data structures, math, sortings

You are given an array $$$a_1, a_2, \dots, a_n$$$. All $$$a_i$$$ are pairwise distinct.

Let's define function $$$f(l, r)$$$ as follows:

- let's define array $$$b_1, b_2, \dots, b_{r - l + 1}$$$, where $$$b_i = a_{l - 1 + i}$$$;
- sort array $$$b$$$ in increasing order;
- result of the function $$$f(l, r)$$$ is $$$\sum\limits_{i = 1}^{r - l + 1}{b_i \cdot i}$$$.

Calculate $$$\left(\sum\limits_{1 \le l \le r \le n}{f(l, r)}\right) \mod (10^9+7)$$$, i.e. total sum of $$$f$$$ for all subsegments of $$$a$$$ modulo $$$10^9+7$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the length of array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$, $$$a_i \neq a_j$$$ for $$$i \neq j$$$) — array $$$a$$$.

Output format:
Print one integer — the total sum of $$$f$$$ for all subsegments of $$$a$$$ modulo $$$10^9+7$$$

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Description of the first example:

- $$$f(1, 1) = 5 \cdot 1 = 5$$$;
- $$$f(1, 2) = 2 \cdot 1 + 5 \cdot 2 = 12$$$;
- $$$f(1, 3) = 2 \cdot 1 + 4 \cdot 2 + 5 \cdot 3 = 25$$$;
- $$$f(1, 4) = 2 \cdot 1 + 4 \cdot 2 + 5 \cdot 3 + 7 \cdot 4 = 53$$$;
- $$$f(2, 2) = 2 \cdot 1 = 2$$$;
- $$$f(2, 3) = 2 \cdot 1 + 4 \cdot 2 = 10$$$;
- $$$f(2, 4) = 2 \cdot 1 + 4 \cdot 2 + 7 \cdot 3 = 31$$$;
- $$$f(3, 3) = 4 \cdot 1 = 4$$$;
- $$$f(3, 4) = 4 \cdot 1 + 7 \cdot 2 = 18$$$;
- $$$f(4, 4) = 7 \cdot 1 = 7$$$;

Example input:
4
5 2 4 7

Example output:
167

Example input:
3
123456789 214365879 987654321

Example output:
582491518

Editorial:
Let's define some functions at first: indicator function $$$I(x) = 1$$$ if $$$x$$$ is true and $$$0$$$ otherwise. $$$lower(l, r, x)$$$ is a number of $$$a_j$$$ that $$$l \le j \le r$$$ and $$$a_j < x$$$. Good observation: $$$lower(l, r, x) = \sum_{j = l}^{j = r}{I(a_j < x)}$$$.
Another observation: $$$f(l, r) = \sum\limits_{i = l}^{i = r}{a_i \cdot (lower(l, r, a_i) + 1})$$$.
Now, it's time to transform what we'd like to calculate: $$$$$$\sum_{1 \le l \le r \le n}{f(l, r)} = \sum_{1 \le l \le r \le n}{\sum_{i = l}^{i = r}{a_i \cdot (lower(l, r, a_i) + 1})} = \sum_{1 \le l \le r \le n}{(\sum_{i = l}^{i = r}{a_i \cdot lower(l, r, a_i)} + \sum_{i = l}^{i = r}{a_i})} = \\ = \sum_{1 \le l \le r \le n}{\sum_{i = l}^{i = r}{a_i \cdot lower(l, r, a_i)}} + \sum_{i = 1}^{i = n}{a_i \cdot i \cdot (n - i + 1)}$$$$$$
Since transformation of the second sum was standard, we'll look at the first sum: $$$$$$\sum_{1 \le l \le r \le n}{\sum_{i = l}^{i = r}{a_i \cdot lower(l, r, a_i)}} = \sum_{i = 1}^{i = n}{\sum_{1 \le l \le i \le r \le n}{a_i \cdot lower(l, r, a_i)}} = \sum_{i = 1}^{i = n}{a_i \sum_{1 \le l \le i \le r \le n}{lower(l, i, a_i) + lower(i, r, a_i)}} = \\ = \sum_{i = 1}^{i = n}{a_i \sum_{1 \le l \le i}{ \sum_{i \le r \le n}{lower(l, i, a_i) + lower(i, r, a_i)}}} = \sum_{i = 1}^{i = n}{a_i \left( (n - i + 1) \sum_{1 \le l \le i}{lower(l, i, a_i)} + i \sum_{i \le r \le n}{lower(i, r, a_i)} \right) }$$$$$$
So, we can iterate over $$$i$$$ and we'd like to calculate this two sums fast enough. So, more transformations: $$$$$$\sum_{1 \le l \le i}{lower(l, i, a_i)} = \sum_{1 \le l \le i}{\sum_{j = l}^{j = i}{I(a_j < a_i)}} = \sum_{j = 1}^{j = i}{\sum_{l = 1}^{l = j}{I(a_j < a_i)}} = \sum_{j = 1}^{j = i}{I(a_j < a_i) \cdot j}$$$$$$
So, while iterating over $$$i$$$ we need to make queries of two types: set value $$$i$$$ in position $$$a_i$$$ and calculate $$$\sum_{a_j < a_i}{j}$$$. It can be done by BIT with coordinate compression.
$$$\sum_{i \le r \le n}{lower(i, r, a_i)}$$$ can be calculated in the same way iterating over $$$i$$$ in reverse order.
Result complexity is $$$O(n \log{n})$$$.