Sereja and Data Structures
All submissions for this problem are available.
Sereja is a little student from the University of Kyiv. He studies computer science. He is rather experienced programmer and he knows a lot of advanced algorithms. The only thing he likes more than advanced algorithms is segment tree data structure.
Every evening he goes to the loveliest place in Kyiv - The Chef's cafe. Chef is also interested in computer science, so they often discuss different problems. Last evening Sereja told Chef following problem: given an array A1, A2, ..., AN of N integers. The task is to find the product of ranges of the segments [i, j] over 1 ≤ i < j ≤ N, where the range of the segment [i, j] means max(Ai, Ai+1, ..., Aj) - min(Ai, Ai+1, ..., Aj).
Both Sereja and Chef couldn't find any efficient algorithm for this problem with segment tree. They gave up thinking of it, and Chef said we may calculate this value only for a random array, that means all elements of the array are generated uniformly and independently at random. Sereja were surprised to hear that, and he wanted to know about details. However Chef is very busy at the moment, so he asked you to solve this problem for a random array.
The first line contains a single integer N, then N integers A1, A2, ..., AN follow on the second line.
Output a single line containing the required product modulo 1000000007 (109+7), since the answer can be very large.
2 ≤ N ≤ 100000 (105)
0 ≤ Ai < 1000000007 (109+7)
All test cases, except Example, are created by the method described in Test Case Generation.
Input 1: 3 1 2 4 Output 1: 6 Input 2: 5 5 5 5 5 5 Output 2: 0
In Input 1, we should consider 3 segments [i, j] = [1, 2], [2, 3], [1, 3].
The range of segment [1, 2] is max(1,2) - min(1,2) = 1.
The range of segment [2, 3] is max(2,4) - min(2,4) = 2.
The range of segment [1, 3] is max(1,2,4) - min(1,2,4) = 3.
Therefore, we obtain the answer 1 * 2 * 3 = 6, and you should output 6 mod 1000000007 = 6.
In Input 2, we should consider 10 segments, but all ranges of such segments are 0. And, of course, the answer is 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 = 0.
Note that Example is created by manually, so these arrays are not random arrays. It is quite unlikely that the official test cases contain an array with equal elements such as Input 2.
Test Case Generation
There are 15 official test files.For every test file, Ai are chosen from 0 to 1000000006 (109+6) uniformly and independently at random.
The first 5 test files: N is chosen from 2 to 100 uniformly at random.
The next 5 test files: N is chosen from 2 to 100000 (105) uniformly at random.
The last 5 test files: N = 100000 (105)
|Tags||Rubanenko, dec12, medium, simple-math|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.