// 誤解法チェック
ll@N,@K,A[2K],o=0,m,r=2N+1,t;rep(i,K)A[i+K]=(A[i]=rd_ll())+2N;while(o<r-1){m=(o+r)/2;REP(j,*A+1,A[1]){t=j;rep(i,1,K){if(A[i+1]<=t+m)t=5N,break;t=max(A[i]+1,t+m);}if(t+m<=j+2N)o=m,break;}o<m?r=m:r;}wt(o);