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 \neq 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 \(10^9 + 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 \(10^9+7\).
Constraints
\(2 \le N \le 10^5 \)
\(-10^{18} \le A[i] \le 10^{18}\)
4 1 -9 2 -1
22
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\).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor