Fredo is assigned a task today. He is given an array A containing N integers. His task is to update all elements of array to some minimum value x, that is, \(A[i]=x\) ; \(1≤i≤N\) such that product of all elements of this new array is strictly greater than the product of all elements of the initial array. Note that x should be as minimum as possible such that it meets the given condition. Help him find the value of x.
Input Format:
The first line consists of an integer N , denoting the number of elements in the array.
The next line consists of N space separated integers, denoting the array elements.
Output Format:
The only line of output consists of value of x.
Input Constraints:
\(1 \le N \le 10^5\)
\(1 \le A[i] \le 10^{10}\); \(A[i]\) denoting an array element.
Initial array product \(= 4 * 2 * 1 * 10 *6 = 480\)
If all elements become 4, then product \(= 4 * 4 * 4 * 4 * 4 = 1024\). Had all elements become 3, product would be \(= 243\) which is less than \(480\). Hence, value of x is 4.
