M=2000;eval"N,*C="+`dd`.split*?,;b=C.pop(N);p b.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