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 much-needed 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.
The first line of the input contains a single integer N denoting the number of elements in the list.
The second line contains N space-separated integers L1, L2, ..., LN denoting the elements of the list.
Ouput an integer corresponding to the answer to the only test case in a line.
- 1 ≤ N ≤ 106
- 1 ≤ Li ≤ 109
Input: 3 2 1 3 Output: 19
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.
|Tags||cook84, medium, prateekg603|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.