class TwoByTwoMatrix: zero=None one=None def __init__(self,M00,M01,M10,M11): self.M00 = M00 self.M01 = M01 self.M10 = M10 self.M11 = M11 def copy(self): return self.__class__(self.M00,self.M01,self.M10,self.M11) def __eq__(self,other): return self.M00 == other.M00 and self.M01 == other.M01 and self.M10 == other.M10 and self.M11 == other.M11 def __ne__(self,other): return not( self == other ) def __iadd__(self,other): self.M00 += other.M00 self.M01 += other.M01 self.M10 += other.M10 self.M11 += other.M11 return self def __add__(self,other): M = self.copy() M += other return M def __isub__(self,other): self.M00 -= other.M00 self.M01 -= other.M01 self.M10 -= other.M10 self.M11 -= other.M11 return self def __sub__(self,other): M = self.copy() M -= other return M def __neg__(self): return self.__class__(-self.M00,-self.M01,-self.M10,-self.M11) def __mul__(self,other): return self.__class__(self.M00 * other.M00 + self.M01 * other.M10,self.M00 * other.M01 + self.M01 * other.M11,self.M10 * other.M00 + self.M11 * other.M10,self.M10 * other.M01 + self.M11 * other.M11) def __imul__(self,other): self.M00 , self.M01 , self.M10 , self.M11 = self.M00 * other.M00 + self.M01 * other.M10 , self.M00 * other.M01 + self.M01 * other.M11 , self.M10 * other.M00 + self.M11 * other.M10 , self.M10 * other.M01 + self.M11 * other.M11 return self def ScalarMultiply(self,x): self.M00 *= x self.M01 *= x self.M10 *= x self.M11 *= x return self def det(self): return self.M00 * self.M11 - self.M01 * self.M10 def tr(self): return self.M00 + self.M11 def Adjugate(self): return self.__class__( self.M11 , - self.M01 , - self.M10 , self.M00 ) def Inverse(self): return self.Adjugate().ScalarMultiply( 1 / self.det() ) #d = self.det() #assert( d in [1,-1] ) #For the case of integer coefficients #return self.Adjugate().ScalarMultiply( d ) def __truediv__(self,other): return self * other.Inverse() def __itruediv__(self,other): self *= other.Inverse() return self def __pow__(self,n): #Supported only when n>=0 answer = self.__class__.one.copy() power = self.copy() while n > 0: if n&1:answer *= power power.Square() n >>= 1 return answer def __xor__(self,n): return self.Inverse()**(-n)if n < 0 else self ** n #private: def Square(self): self.M00 , self.M01 , self.M10 , self.M11 = self.M00 ** 2 + self.M01 * self.M10 , ( self.M00 + self.M11 ) * self.M01 , self.M10 * ( self.M00 + self.M11 ) , self.M10 * self.M01 + self.M11 ** 2 TwoByTwoMatrix.zero = TwoByTwoMatrix(0,0,0,0) #User's definition TwoByTwoMatrix.one = TwoByTwoMatrix(1,0,0,1) #User's definition class TwoByOneMatrix: zero=None def __init__(self,M0,M1): self.M0 = M0 self.M1 = M1 def copy(self): return self.__class__(self.M0,self.M1) def __eq__(self,other): return self.M0 == other.M0 and self.M1 == other.M1 def __ne__(self,other): return not( self == other ) def __iadd__(self,other): self.M0 += other.M0 self.M1 += other.M1 return self def __add__(self,other): M = self.copy() M += other return M def __isub__(self,other): self.M0 -= other.M0 self.M1 -= other.M1 return self def __sub__(self,other): M = self.copy() M -= other return M def __neg__(self): return self.__class__(-self.M0,-self.M1) def __rmul__(self,T): return self.copy().Act(T) def Act(self,T,n=1): if n==1:T.M00 * self.M0 + T.M01 * self.M1 , T.M10 * self.M0 + T.M11 * self.M1 elif n: if n>0:p = T.copy() else:n , p = -n , T.Inverse() while n: if n&1:self.M0 , self.M1 = p.M00 * self.M0 + p.M01 * self.M1 , p.M10 * self.M0 + p.M11 * self.M1 n >>= 1 p.Square() return self def ScalarMultiply(self,x): self.M0 *= x self.M1 *= x return self TwoByOneMatrix.zero = TwoByOneMatrix(0,0) #User's definition J=lambda:map(int,input().split()) N,*_=J() A=list(J()) U=TwoByTwoMatrix(2,-1,1,0) L=TwoByTwoMatrix(0,1,-1,2) def f(i): global min;global max;l,r=0,1<<62 if A[i]max:A[i],max=max,A[i] if A[i]*2>1;w=v.copy() if w.Act(U,m).M0>max:r=m else:l=m v.Act(U,l) A[i],min=v.M0,v.M1 else: v=TwoByOneMatrix(max,A[i]) while l>1;w=v.copy() if w.Act(L,m).M1