n,*_=`dd`.split.map &:to_i;b=_.pop(n);p b.map{a=_.sort.map{|v|v*M=2000};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