Question
Peak Pair
Zara holds an array B of size M. For each index j (1 ≤ j ≤ M), compute the product of the two largest numbers in the subarray from indices 1 to j.
Input
The first line of the input contains a single integer M.
The second line of the input contains M space-separated integers.
The second line of the input contains M space-separated integers.
Output
Print M integers - for each integer i (1 ≤ i ≤ M), print the product of the largest two integers in the range of indices [1, i] in the array.
NOTE: If there don't exist two numbers in the given range, print -1 for that particular index.
NOTE: If there don't exist two numbers in the given range, print -1 for that particular index.
Example
Sample Input
5
3 5 4 1 9
Sample Output
-1 15 20 20 45
Explanation
For
i = 1, there is only one element, hence -1
i = 2 -> 3 and 5 are the two largest elements, hence 3 * 5 = 15
i = 3 -> 4 and 5 are the two largest elements, hence 4 * 5 = 20
and so on..
5
3 5 4 1 9
Sample Output
-1 15 20 20 45
Explanation
For
i = 1, there is only one element, hence -1
i = 2 -> 3 and 5 are the two largest elements, hence 3 * 5 = 15
i = 3 -> 4 and 5 are the two largest elements, hence 4 * 5 = 20
and so on..