M=2000;eval"N,*C="+`dd`.split*?,;p (b=C.pop N).map{a=C.sort.map{|v|v*M};b.rotate!.map{|l|m=a.shift+l/2*M+1;a.insert a.bsearch_index{|v|v>m}||-1,m};a.map{|v|v%M}.max}.min