Product of Array Except Self

Given an array of integers, you are required to return an array where each element at index (i) is equal to the product of all the numbers in the original array except the one at (i).

Note that you must solve the problem without using division and in (O(n)) time complexity. This problem tests your ability to perform accumulative product scans from both left to right and right to left.

inputFormat

The first line contains a single integer (n) ((2 \leq n \leq 10^5)), representing the number of elements in the array.

The second line contains (n) space-separated integers (a_1, a_2, \dots, a_n) where (|a_i| \leq 10^9).

outputFormat

Output (n) space-separated integers where the (i)-th integer is the product of all the elements of the input array except the (i)-th element.## sample

4
1 2 3 4

24 12 8 6