You are given an array A of N integers. For every index i of the array A, you need to select an index j such that j≠i and the product of A[i] and A[j] is maximum for that i . Finally, you need to print the sum of A[i]∗A[j] for all the indices i . Since this sum can be large, you need to print it to the modulo 109+7.
Note: Please refer to the sample explanation section.
Input format
- First line: Integer N denoting the number of elements in the array A
- Next line: N space-separated integers denoting the elements of the array A
Output format
Print the required sum to the modulo 109+7.
Constraints
2≤N≤105
−1018≤A[i]≤1018
For an element with the index 1, you can choose another index as 3, so its maximum product will be 1∗2=2
For an element with the index 2, you can choose another index as 4, so its maximum product will be −9∗−1=9
For an element with the index 3, you can choose another index as 1, so its maximum product will be 2∗1=2
For an element with the index 4, you can choose another index as 2, so its maximum product will be −1∗−9=9
Hence, the final answer will be 2+9+2+9=22.
