Chang and Perfect Quadruples

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
Chang was not able to sleep well last night as he was thinking about a problem which still remains unsolved. Since he has only a day left to solve this problem and hand it to the interviewer, you being his friend decide to help him solve this so that he can clear this round and get a muchneeded job. The problem is as follows.
Given a list L of N integers, Chang defines a perfect quadruple (i, j, k, l) such that:
 i, j, k, l are the indices of the list
 i ≤ j < k ≤ l
You need to find the summation of F(i, j, k, l) over all perfect quadruples (i, j, k, l). F(i, j, k, l) is calculated as the product of maximum element in range [i, j] and the minimum element in range [k, l]. Since, the answer can be large, print it modulo 10^9 + 7.
Input
The first line of the input contains a single integer N denoting the number of elements in the list.
The second line contains N spaceseparated integers L_{1}, L_{2}, ..., L_{N} denoting the elements of the list.
Output
Ouput an integer corresponding to the answer to the only test case in a line.
Constraints
 1 ≤ N ≤ 10^{6}
 1 ≤ L_{i} ≤ 10^{9}
Example
Input: 3 2 1 3 Output: 19
Explanation
The perfect Quadruples and their individual contribution is calculated as.
F(1, 1, 2, 2) = 2*1 = 2 F(1, 1, 2, 3) = 2*1 = 2 F(1, 1, 3, 3) = 2*3 = 6 F(1, 2, 3, 3) = 2*3 = 6 F(2, 2, 3, 3) = 1*3 = 3
All these values sum up to 19.
Author:  prateekg603 
Editorial  https://discuss.codechef.com/problems/CHNGSUM 
Tags  cook84, medium, prateekg603 
Date Added:  25062017 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 