trojke
A math teacher gave the following problem to Dragance. Based on the following array of numbers a[1], a[2] ,…, a[n] , Dragance has to write on the board the highest of the numbers ai, aj and ak for every triplet of the indeces (i,j,k) where 1<i<j<k<n. Then, he has to find out the sum of all the numbers written on the board modulo 10007. The teacher has promised Dragance the best mark at the end of the school year if he gets the right result by the end of the class. Help Dragance get the result as soon as possible.
InputThe first line of the standart input contains a number n (3<n<30000). In the next n lines there are integers a[1] , a[2] , ..., a[n] , where -100000<a[i]<100000.
OutputTo the standart output in the first and only line write the sum of the numbers writen on the table modulo 10007.
Input:
Output:
Explanation: All triplets of the given array of numbers are: (3, -1, 2), (3, -1, 2), (3, 2, 2), (-1, 2, 2). The numbers writen on the board are 3, 3, 3, 2, so the solution in this case is 11.
4
3
-1
2
2Output:
11Explanation: All triplets of the given array of numbers are: (3, -1, 2), (3, -1, 2), (3, 2, 2), (-1, 2, 2). The numbers writen on the board are 3, 3, 3, 2, so the solution in this case is 11.
Input:
Output:
6
8
-10
4
5
2
6Output:
135Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.