Product of Array Except Self

Given an array of integers, your task is to compute a new array such that each element at index (i) is equal to the product of all the numbers in the original array except the one at (i).

You must solve the problem in (O(n)) time complexity without using division. This means you should construct your solution using two passes over the array: one pass to compute the products of elements to the left of each index, and one pass to compute the products of elements to the right.

inputFormat

Standard Input consists of two lines.

The first line contains an integer (n), representing the number of elements in the array.
The second line contains (n) space-separated integers representing the array elements.

outputFormat

Output a single line containing (n) space-separated integers, where the (i^{th}) integer is the product of all the numbers in the input array except the one at index (i).## sample

4
1 2 3 4

24 12 8 6