CF1167F Scalar Queries

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 $ .

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 $ .

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

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 $ ;