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≤N≤105
1≤A[i]≤1010; 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.
